Computing a minimum paired-dominating set in strongly orderable graphs

DOI10.1016/j.dam.2018.08.022zbMath1401.05223OpenAlexW2897850773WikidataQ129097715 ScholiaQ129097715MaRDI QIDQ1634760

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

polynomial time algorithmdominationpaired-dominationstrongly orderable graphs

Mathematics Subject Classification ID

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

Related Items (6)

A linear-time algorithm for weighted paired-domination on block graphs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ Paired Domination in Graphs ⋮ Upper paired domination versus upper domination

Cites Work

• Unnamed Item
• Unnamed Item
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• \(L(2,1)\)-labeling of dually chordal graphs and strongly orderable graphs
• Labelling algorithms for paired-domination problems in block and interval graphs
• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Complexity of distance paired-domination problem in graphs
• An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
• Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
• A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
• Labelling Graphs with a Condition at Distance 2
• Paired-domination in graphs

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