Exact algorithms for weak Roman domination

DOI10.1016/j.dam.2017.09.015zbMath1395.05168OpenAlexW2767334193MaRDI QIDQ2413969

Mathieu Chapelle, Anthony Perez, Dieter Kratsch, Romain Letourneur, Jean-François Couturier, Manfred Cochefert, Mathieu Liedloff

Publication date: 17 September 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.09.015

zbMATH Keywords

graph algorithminterval graphsexact algorithmRoman domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

On the \(k\)-strong Roman domination problem ⋮ Varieties of Roman Domination ⋮ An algorithm to recognize weak roman domination stable trees under vertex deletion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact algorithms for dominating set
• A note on Roman domination in graphs
• Finding a dominating set on bipartite graphs
• Efficient algorithms for Roman domination on some classes of graphs
• On the Roman domination number of a graph
• Secure domination critical graphs
• Linear time algorithms on circular-arc graphs
• Efficient graph representations
• Roman domination in graphs.
• Defending the Roman Empire---a new strategy
• Some results on roman domination edge critical graphs
• Tight bounds for eternal dominating sets in graphs
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• Exact Algorithms for Weak Roman Domination
• A Faster Algorithm for Dominating Set Analyzed by the Potential Method
• Roman Domination on 2-Connected Graphs
• Weak Roman domination in graphs
• A measure & conquer approach for the analysis of exact algorithms
• Extremal Problems for Roman Domination

This page was built for publication: Exact algorithms for weak Roman domination