Computing a minimum paired-dominating set in strongly orderable graphs

DOI10.1016/J.DAM.2018.08.022MaRDI QIDQ1634760zbMATH OpenOpenAlexWikidataFDO

Authors Y. Aharonov

Publication date 18 December 2018

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

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

zbMATH Keywords

dominationpaired-dominationpolynomial time algorithmstrongly orderable graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• Paired-domination problem on distance-hereditary graphs

Cites work

• \(L(2,1)\)-labeling of dually chordal graphs and strongly orderable graphs
• A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
• Complexity of distance paired-domination problem in graphs
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Labelling algorithms for paired-domination problems in block and interval graphs
• Labelling Graphs with a Condition at Distance 2
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• Paired-domination in graphs
• Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs

Cited in

(10)

• Complexity of paired domination in AT-free and planar graphs
• A linear-time algorithm for weighted paired-domination on block graphs
• Algorithmic aspects of upper paired-domination in graphs
• A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
• Paired domination in graphs
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• Upper paired domination versus upper domination
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• A linear-time algorithm for paired-domination problem in strongly chordal graphs

This page was built for publication: Computing a minimum paired-dominating set in strongly orderable graphs

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