Return to search

Connected domination in graphs

A connected dominating set D is a set of vertices of a graph G=(V,E) such that every vertex in V-D is adjacent to at least one vertex in D and the subgraph induced by the set D is connected. The connected domination number is the minimum of the cardinalities of the connected dominating sets of G. The problem of finding a minimum connected dominating set D is known to be NP-hard. Many polynomial time algorithms that achieve some approximation factors have been provided earlier in finding a minimum connected dominating set. In this work, we present a survey on known properties of graph domination as well as some approximation algorithms. We implemented some of these algorithms and tested them with random graphs and compared their performance in finding a minimum connected dominating set D.

Identiferoai:union.ndltd.org:USF/oai:scholarcommons.usf.edu:etd-3973
Date01 January 2005
CreatorsMahalingam, Gayathri
PublisherScholar Commons
Source SetsUniversity of South Flordia
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceGraduate Theses and Dissertations
Rightsdefault

Page generated in 0.0017 seconds