Paper Info
Title
Greedy Approximation For The Minimum Connected Dominating Set With Labeling
Abstract
Given a connected graphG=(V,E). A subset C subset of V is adominating setif every vertex ofVis either inCor adjacent to a vertex inC. Further,Cis aconnected dominating setifCis a dominating set and the induced subgraphG[C] is connected. The Minimum Connected Dominating Set (Min-CDS) problem asks to find a connected dominating set with the minimum size, which finds applications in communication networks, in particular, as a virtual backbone in wireless sensor networks. This paper focuses on a variant of the classic Min-CDS problem, called Minimum Connected Dominating Set with Labeling (Min-CDSL), in which we are given a connected graph with vertex labels, and are required to find a connected dominating setCsuch that the number of labels in C(instead of |C|) is minimized. Min-CDSL is apparently a generalization of Min-CDS, and is undoubtedly NP-complete. We give an approximation algorithm for Min-CDSL within performance ratio bounded byln|V(G)|+span(G)+1ln |V(G)|+span(G)+, wherespan(G) refers to the maximumspanof the input labeled graph (i.e., the number of connected components of the induced subgraph by a single label). In general, span(G) is an element of|V(G)| and for a series of labeled graphsspan(G)=O(1) (G)=O(1).For a random graphG is an element of Gn,p ,span(G)=O(ln|V(G)|) (G)=O(\ln |V(G)|) almost surely, and thus our approximation ratio isO(ln|V(G)|) which is reasonable comparing with the best known approximation ratioln|V(G)|+1 for Min-CDS.
Year
DOI
Venue
2021
10.1007/s11590-020-01628-6
OPTIMIZATION LETTERS
Keywords
DocType
Volume
Greedy algorithm, Connected dominating set, Approximation algorithm, Performance ratio, Labeling
Journal
15
Issue
ISSN
Citations 
2
1862-4472
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Zishen Yang101.01
Majun Shi200.68
Wei Wang38112.64