Algorithm and complexity of the two disjoint connected dominating sets problem on trees
DOI10.1016/j.amc.2018.05.037zbMath1427.68250OpenAlexW2807979137MaRDI QIDQ2335669
Zishen Yang, Xianliang Liu, Wei Wang
Publication date: 15 November 2019
Published in: Applied Mathematics and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.amc.2018.05.037
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Connectivity (05C40)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Dominating and total dominating partitions in cubic graphs
- Remarks about disjoint dominating sets
- A minimum 3-connectivity augmentation of a graph
- Approximation algorithms for connected dominating sets
- A smallest augmentation to 3-connect a graph
- An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees
- On the optimal vertex-connectivity augmentation
- Pairs of disjoint dominating sets and the minimum degree of graphs
- Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets
- Partitioning a graph into a dominating set, a total dominating set, and something else
- A Characterization of Graphs with Disjoint Dominating and Total Dominating Sets
- The minimum augmentation of any graph to aK-edge-connected graph
- On Four-Connecting a Triconnected Graph
- Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems
This page was built for publication: Algorithm and complexity of the two disjoint connected dominating sets problem on trees
