Complexity of paired domination in at-free and planar graphs

DOI10.1007/978-3-030-95018-7_6arXiv2112.05486OpenAlexW4225525972MaRDI QIDQ6102264

Arti Pandey, Kaustav K. Paul, Ton Kloks, Vikash Tripathi, Hung-Lung Wang

Publication date: 8 May 2023

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2112.05486

zbMATH Keywords

approximation algorithmplanar graphsNP-completenessgraph algorithmsdominationpaired dominationat-free graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (4)

Complexity of paired domination in AT-free and planar graphs ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Linear-time algorithm for paired-domination on distance-hereditary graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• Labelling algorithms for paired-domination problems in block and interval graphs
• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• Face covers and the genus problem for apex graphs
• An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
• Domination and total domination on asteroidal triple-free graphs
• Paired-domination problem on distance-hereditary graphs
• A linear-time algorithm for paired-domination on circular-arc graphs
• Asteroidal Triple-Free Graphs
• Paired-domination in graphs
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• Topics in Domination in Graphs
• Approximating the bandwidth for asteroidal triple-free graphs

This page was built for publication: Complexity of paired domination in at-free and planar graphs