Domination problems on P₅-free graphs

DOI10.1051/ITA/2014026MaRDI QIDQ5248877zbMATH OpenOpenAlexFDO

Authors Min Chih Lin, Michel J. Mizrahi

Publication date 28 April 2015

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1051/ita/2014026

zbMATH Keywords

\({P}_{5}\)-free graphsdominating setRoman dominating function

Mathematics Subject Classification ID

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

Recommendations

• Algorithmic aspects of Roman domination in graphs
• Efficient algorithms for Roman domination on some classes of graphs
• Graph-Theoretic Concepts in Computer Science
• Perfect Roman domination in graphs
• Complexity issues of perfect Roman domination in graphs

Cites work

• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Arboricity and Subgraph Listing Algorithms
• Dominating cliques in \(P_ 5\)-free graphs
• Dominating sets for split and bipartite graphs
• Dominating Sets in Chordal Graphs
• Domination and total domination on asteroidal triple-free graphs
• Domination in Graphs Applied to Electric Power Networks
• Domination in permutation graphs
• Efficient algorithms for Roman domination on some classes of graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1933051 (Why is no real title available?)
• Lower Bounds and Algorithms for Dominating Sets in Web Graphs
• Roman domination in graphs.
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs

Cited in

(2)

• A note on efficient domination in a superclass of \(P_5\)-free graphs
• Domination number of graphs with minimum degree five

This page was built for publication: Domination problems on \(P_{5}\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5248877)