Complexity of paired domination in AT-free and planar graphs
From MaRDI portal
Publication:2166758
DOI10.1016/j.tcs.2022.07.010OpenAlexW4200630549MaRDI QIDQ2166758
Vikash Tripathi, Arti Pandey, Hung-Lung Wang, Ton Kloks, Kaustav K. Paul
Publication date: 25 August 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2112.05486
approximation algorithmplanar graphsNP-completenessgraph algorithmsdominationAT-free graphspaired domination
Related Items (1)
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
- Perfectly relating the domination, total domination, and paired domination numbers of a graph
- A linear-time algorithm for paired-domination on circular-arc graphs
- Representation of a finite graph by a set of intervals on the real line
- The Complexity of Multiterminal Cuts
- Asteroidal Triple-Free Graphs
- Paired-domination in graphs
- Linear time algorithms for dominating pairs in asteroidal triple-free graphs
- Total Domination in Graphs
- Topics in Domination in Graphs
- Transitiv orientierbare Graphen
- Complexity of paired domination in at-free and planar 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
