LAUSR

Given a connected graph $$G=(V,E)$$ G = ( V , E ) . A subset $$C\subseteq V$$ C ⊆ V is a dominating set if every vertex of V is either in C or adjacent to a vertex in C . Further, C is a connected dominating set if C is a dominating set and the induced subgraph G [ 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 set C such that the number of labels in C (instead of | C |) is minimized. Min-CDSL is apparently a generalization of Min-CDS, and is undoubtedly $$\mathcal {NP}$$ NP - $$\mathrm {complete}$$ complete . We give an approximation algorithm for Min-CDSL within performance ratio bounded by $$\ln |V(G)|+\mathrm {span}(G)+1$$ ln | V ( G ) | + span ( G ) + 1 , where $$\mathrm {span}(G)$$ span ( G ) refers to the maximum span of the input labeled graph (i.e., the number of connected components of the induced subgraph by a single label). In general, $$\mathrm {span}(G)\ll |V(G)|$$ span ( G ) ≪ | V ( G ) | and for a series of labeled graphs $$\mathrm {span}(G)=O(1)$$ span ( G ) = O ( 1 ) . For a random graph $$G\in {G_{n,p}}$$ G ∈ G n , p , $$\mathrm {span}(G)=O(\ln |V(G)|)$$ span ( G ) = O ( ln | V ( G ) | ) almost surely, and thus our approximation ratio is $$O(\ln |V(G)|)$$ O ( ln | V ( G ) | ) which is reasonable comparing with the best known approximation ratio $$\ln |V(G)|+1$$ ln | V ( G ) | + 1 for Min-CDS.