Efficient algorithms for Roman domination on some classes of graphs

DOI10.1016/j.dam.2008.01.011zbMath1180.05113OpenAlexW2013474931MaRDI QIDQ1003729

Sheng-Lung Peng, Ton Kloks, Mathieu Liedloff, Ji Ping Liu

Publication date: 4 March 2009

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

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

zbMATH Keywords

graph algorithmscographsAT-free graphsinterval graphsRoman dominationweight of a Roman dominating function

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (33)

A note on the Roman domatic number of a digraph ⋮ Computing Roman domatic number of graphs ⋮ Algorithmic aspects of total Roman and total double Roman domination in graphs ⋮ Roman domination dot-critical graphs ⋮ A note on the bounds of Roman domination numbers ⋮ Roman domination in subgraphs of grids ⋮ Total Roman \(\{2\}\)-dominating functions in graphs ⋮ Vertex-addition strategy for domination-like invariants ⋮ Triple Roman domination in graphs ⋮ On the signed Roman \(k\)-domination: complexity and thin torus graphs ⋮ Roman domination on strongly chordal graphs ⋮ Exact algorithms for weak Roman domination ⋮ On the outer independent total double Roman domination in graphs ⋮ Minimal Roman dominating functions: extensions and enumeration ⋮ Unique response Roman domination: complexity and algorithms ⋮ Complexity aspects of restrained Roman domination in graphs ⋮ Algorithmic results in Roman dominating functions on graphs ⋮ On the \(k\)-strong Roman domination problem ⋮ Perfect Italian domination on planar and regular graphs ⋮ Weak \(\{2\}\)-domination number of Cartesian products of cycles ⋮ Maximal double Roman domination in graphs ⋮ Algorithmic Aspects of Quasi-Total Roman Domination in Graphs ⋮ ON THE ROMAN BONDAGE NUMBER OF A GRAPH ⋮ A continuous generalization of domination-like invariants ⋮ Roman Domination in Graphs ⋮ Algorithmic aspects of Roman domination in graphs ⋮ Roman domination in graphs: The class ℛUV R ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs ⋮ Domination problems on P₅-free graphs ⋮ Restrained condition on double Roman dominating functions ⋮ Algorithmic complexity of weakly connected Roman domination in graphs ⋮ Quadruple Roman domination in graphs ⋮ ALGORITHMIC ASPECTS OF ROMAN GRAPHS

Cites Work

• Defending the Roman Empire from multiple attacks
• Algorithms for graphs with small octopus
• Roman domination in graphs.
• A simple linear time algorithm for cograph recognition
• Defending the Roman Empire---a new strategy
• Domination and total domination on asteroidal triple-free graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• Graph Classes: A Survey
• Asteroidal Triple-Free Graphs
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• Approximating the bandwidth for asteroidal triple-free graphs

This page was built for publication: Efficient algorithms for Roman domination on some classes of graphs