A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs

DOI10.1142/S1793830915500202MaRDI QIDQ5261054zbMATH OpenOpenAlexFDO

Authors

Publication date 1 July 2015

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830915500202

zbMATH Keywords

dominationNP-completeplanar graphsproper interval graphsrestrained dominationchordal bipartite graphsundirected path graphscircle graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Restrained domination in some subclasses of chordal graphs
• Restrained domination in graphs
• NP-completeness and APX-completeness of restrained domination in graphs
• Restrained and total restrained domination in cographs
• Weighted restrained domination in subclasses of planar graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A linear time recognition algorithm for proper interval graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• Graph Classes: A Survey
• Incidence matrices and interval graphs
• NP-completeness and APX-completeness of restrained domination in graphs
• Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs
• Restrained domination in claw-free graphs with minimum degree at least two
• Restrained domination in graphs
• Restrained domination in trees
• Restrained domination in unicyclic graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The complexity of domination problems in circle graphs
• Trees with equal domination and restrained domination numbers

Cited in

(8)

• Injective coloring of some subclasses of bipartite graphs and chordal graphs
• Weighted restrained domination in subclasses of planar graphs
• Restrained and total restrained domination in cographs
• Restrained domination in some subclasses of chordal graphs
• Linear algorithm for domatic number problem on interval graphs
• Restrained domination and its variants in extended supergrid graphs
• A linear algorithm for double Roman domination of proper interval graphs
• New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs

This page was built for publication: A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs

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