Home

 

Recent Issues

 

Volume 47

1

 

 

 

Volume 46

1

2

3

4

Volume 45

1&2

3

4

Volume 44

1

2

3

4

Volume 43

1

2

3

4

 

Past Issues

 

The Journal

Cover

Aims and Scope

Subscription Information

Editorial Board

Instructions for Author

Contact Us

 

 

 

 

 

 

 

Vietnam Journal of Mathematics 38:2 (2010) 157-168  

Minimum Connected Dominating Sets in Finite Graphs

Le Cong Thanh

Abstract.  The minimum connected dominating set problem asks for a minimum size subset of vertices with the following property: each vertex is required to be either in the subset, or adjacent to some vertex in the subset, and the subgraph induced by the subset is connected. This problem is known to be NP-hard and, for any small ε > 0, it cannot be solved by a polynomial time approximation algorithm with the performance ratio less than (1 - ε)ln |V| for any graph G = (V, E) unless P = NP.

The present work deals with almost-every-case analysis of a simple greedy algorithm for this problem. We show that for almost every graph instance G = (V, E) of the problem, the greedy algorithm produces a connected dominating set with at most log|V| vertices and achieves the performance ratio less than 1+\frac{3log|V|}{log|V|}. Thus in almost every-case, the algorithm finds in polynomial time a solution that is extremely close to optimal.

2000 Mathematics Subject Classification: 68Q17.

Keywords: Dominating set, greedy algorithm, performance ratio.

 

 

Established by Vietnam Academy of Science and Technology & Vietnam Mathematical Society

Published by Springer since January 2013