Note
A greedy approximation for minimum connected dominating sets

https://doi.org/10.1016/j.tcs.2004.08.013Get rights and content
Under an Elsevier user license
open archive

Abstract

Given a graph, a connected dominating set is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum connected dominating set is such a vertex subset with minimum cardinality. In this paper, we present a new one-step greedy approximation with performance ratio lnδ+2 where δ is the maximum degree in the input graph. The interesting aspect is that the greedy potential function of this algorithm is not supmodular while all previously known one-step greedy algorithms with similar performance have supmodular potential functions.

Keywords

Connected dominating set
Greedy approximation

Cited by (0)

1

Support in part by Hong Kong Research Grant Council under grant. Cityll 1149/04E and National Science Foundation under grant. ACI-0305567.

2

Support in part by National Science Foundation under grant.