Some results for the two disjoint connected dominating sets problem

DOI10.1142/S1793830919500654zbMath1427.05165MaRDI QIDQ5207499

Wei Wang, Zishen Yang, Xianliang Liu

Publication date: 2 January 2020

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

zbMATH Keywords

cubic graphgirthconnected dominating settwo disjoint connected dominating sets

Mathematics Subject Classification ID

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

Cites Work

• A greedy approximation for minimum connected dominating sets
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Approximation algorithms for connected dominating sets
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Algorithm and complexity of the two disjoint connected dominating sets problem on trees
• Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets
• Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Some results for the two disjoint connected dominating sets problem