EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
267. On a minimum-cost version of double Roman domination
Invited abstract in session WC-29: Optimization issues on graphs I (Contributed), stream Combinatorial Optimization.
Wednesday, 12:30-14:00Room: 157 (building: 208)
Authors (first author is the speaker)
| 1. | Robert Manger
|
| Department of Mathematics, Faculty of Science, University of Zagreb | |
| 2. | Ana Klobučar Barišić
|
| Mathematics, Faculty of Mechanical Engineering and Naval Architecture, University of Zagreb |
Abstract
Double Roman domination (DRD) is an optimization problem posed on an undirected graph. It is formally described as assigning weights to graph vertices according to certain rules. Informally, the problem can be interpreted as allocating some service providers (e.g., military formations) to chosen locations within a geographical area. Thereby the whole service (i.e., response to enemy attacks) should be established in a least expensive way, while still assuring a required “double Roman” level of robustness and reliability. The standard version of DRD treated in the literature identifies the total expense of service with the total number of needed providers.
In this work a new “minimum-cost” version of DRD is considered, which is more general and more realistic than the standard version. It assumes that the actual expenses of providing service can differ from one location to another. Thus, formally speaking, each vertex in our graph is given a cost that is interpreted as the cost of keeping one service provider at the corresponding location.
First, it is noted that the considered minimum-cost DRD problem is NP-hard, not only for general graphs but also for many special graph classes. Next, a dynamic programming algorithm is constructed, which shows that the problem can still be solved in linear time if the involved graph is a tree. Finally, as a solution for general graphs, a heuristic is proposed based on greedy approach and local search.
Keywords
- Graphs and Networks
- Combinatorial Optimization
- Algorithms
Status: accepted
Back to the list of papers