Solving the minimum-cost double Roman domination problem

Ana Klobučar Barišić () and Robert Manger ()
Additional contact information
Ana Klobučar Barišić: University of Zagreb
Robert Manger: Faculty of Science, University of Zagreb

Central European Journal of Operations Research, 2024, vol. 32, issue 3, No 10, 793-817

Abstract: Abstract Double Roman domination (DRD) is a combinatorial optimization problem posed on undirected graphs. It can be interpreted as allocating certain service providers (e.g., military formations, fire brigades or ambulances) to chosen locations within a certain area. Thereby the whole service (i.e., response to enemy attacks, fire or medical urgencies) should be established in a least expensive way, while still assuring a required “double Roman” level of availability and redundancy of providers. The standard version of DRD treated in the literature identifies the total expense of service with the total number of needed providers. In this paper a new “minimum-cost” version of DRD is considered, which is more general and more realistic than the standard version. It takes into account the fact 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 intepreted 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 construction and local search. Performance of both algorithms is evaluated by experiments.

Keywords: Dominating set; Double Roman domination; Minimum cost; Complexity; Dynamic programming; Heuristic; 90C27; 90C35; 05C35; 05C69 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10100-023-00884-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:cejnor:v:32:y:2024:i:3:d:10.1007_s10100-023-00884-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10100

DOI: 10.1007/s10100-023-00884-y

Access Statistics for this article

Central European Journal of Operations Research is currently edited by Ulrike Leopold-Wildburger

More articles in Central European Journal of Operations Research from Springer, Slovak Society for Operations Research, Hungarian Operational Research Society, Czech Society for Operations Research, Österr. Gesellschaft für Operations Research (ÖGOR), Slovenian Society Informatika - Section for Operational Research, Croatian Operational Research Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().