Algorithm and complexity of the two disjoint connected dominating sets problem on trees
type: Item
instance of: scholarly article
title: Algorithm and complexity of the two disjoint connected dominating sets problem on trees
zbMATH Open document ID: 1427.68250
author: Xianliang Liu
author: Zishen Yang
author: Wei Wang
published in: Applied Mathematics and Computation
publication date: 2019-11-15T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7130487
zbMATH Keywords: connected dominating set
zbMATH Keywords: disjoint connected dominating sets
zbMATH Keywords: NP-hard
zbMATH Keywords: approximation algorithm
MaRDI profile type: Publication
full work available at URL: j.amc.2018.05.037
OpenAlex ID: W2807979137
cites work: Approximation algorithms for connected dominating sets
cites work: Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems
cites work: Q3070350
cites work: Remarks about disjoint dominating sets
cites work: Pairs of disjoint dominating sets and the minimum degree of graphs
cites work: Partitioning a graph into a dominating set, a total dominating set, and something else
cites work: Dominating and total dominating partitions in cubic graphs
cites work: Q4206780
cites work: Q4378635
cites work: Q4209364
cites work: Q3615799
cites work: Q4821937
cites work: Augmenting a graph of minimum degree 2 to have two disjoint total dominating sets
cites work: A Characterization of Graphs with Disjoint Dominating and Total Dominating Sets
cites work: On the optimal vertex-connectivity augmentation
cites work: On Four-Connecting a Triconnected Graph
cites work: A minimum 3-connectivity augmentation of a graph
cites work: The minimum augmentation of any graph to aK-edge-connected graph
cites work: A smallest augmentation to 3-connect a graph
cites work: Q4207930
cites work: An optimal time algorithm for the k-vertex-connectivity unweighted augmentation problem for rooted directed trees
DOI: 10.1016/J.AMC.2018.05.037
description: scientific article