Restrained domination in some subclasses of chordal graphs

DOI10.1016/J.ENDM.2017.11.015MaRDI QIDQ2413358zbMATH OpenOpenAlexFDO

Authors Arti Pandey, B. S. Panda

Publication date 10 April 2018

Full work available at URL https://doi.org/10.1016/j.endm.2017.11.015

zbMATH Keywords

NP-completenesschordal graphsdominationrestrained dominationblock graphsdoubly chordal graphs

Mathematics Subject Classification ID

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

Recommendations

• A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
• Restrained domination in graphs
• NP-completeness and APX-completeness of restrained domination in graphs
• On total restrained domination in graphs
• Semipaired Domination in Some Subclasses of Chordal Graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Dually Chordal Graphs
• Restrained domination in graphs

Cited in

(7)

• Exact square coloring of certain classes of graphs: complexity and algorithms
• Weighted restrained domination in subclasses of planar graphs
• A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
• scientific article; zbMATH DE number 48751 (Why is no real title available?)
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Semipaired Domination in Some Subclasses of Chordal Graphs
• Restrained domination and its variants in extended supergrid graphs

This page was built for publication: Restrained domination in some subclasses of chordal graphs

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