{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-3973"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-3973","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"Connected Domination in Graphs","abstract":"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 hDi induced by the set D is connected. The connected domination number γc(G) 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. We present the breadth first search algorithm as a heuristic for finding a connected dominating set whose cardinality is hopefully close to that of a minimum connected dominating set. The algorithm finds a spanning tree T of the graph G = (V, E) using breadth first search, and picks up the non-leaf nodes as the connected dominating set D. There are graphs for which the Breadth first search heuristic does not work so well. We implemented some local optimization procedures that would improve the performance of the breadth first search heuristic in finding the minimum connected dominating set D.","abstract_html":"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 hDi induced by the set D is connected. The connected domination number γc(G) 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. We present the breadth first search algorithm as a heuristic for finding a connected dominating set whose cardinality is hopefully close to that of a minimum connected dominating set. The algorithm finds a spanning tree T of the graph G = (V, E) using breadth first search, and picks up the non-leaf nodes as the connected dominating set D. There are graphs for which the Breadth first search heuristic does not work so well. We implemented some local optimization procedures that would improve the performance of the breadth first search heuristic in finding the minimum connected dominating set D.","abstract_has_math":false,"creators":["Mahalingam, Gayathri"],"institution":"University of South Florida","degree_name":null,"degree_level":"Thesis","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Stephen Suen, Ph.D.","Natasha Jonoska, Ph.D.","Gregory McColm, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2005,"date_issued":"2005-01-01T08:00:00Z","date_published":"2005-01-01T08:00:00Z","updated_at":"2026-11-19T08:35:14Z","subjects":["Connected dominating set","Algorithms","Breadth first search","Random graphs","Local optimization","American Studies","Arts and Humanities"],"languages":["EN-US"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/2961","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/2961","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usf.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usf.edu%3Aetd-3973","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Stephen Suen, Ph.D.","Natasha Jonoska, Ph.D.","Gregory McColm, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Mahalingam, Gayathri"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2005-01-01T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis","M.A."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of South Florida"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Connected dominating set","Algorithms","Breadth first search","Random graphs","Local optimization","American Studies","Arts and Humanities"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["EN-US"]},{"key":"dc:rights.license","label":"Dc Rights License","values":["default"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usf.edu/etd/2961"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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 hDi induced by the set D is connected. The connected domination number γc(G) 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. We present the breadth first search algorithm as a heuristic for finding a connected dominating set whose cardinality is hopefully close to that of a minimum connected dominating set. The algorithm finds a spanning tree T of the graph G = (V, E) using breadth first search, and picks up the non-leaf nodes as the connected dominating set D. There are graphs for which the Breadth first search heuristic does not work so well. We implemented some local optimization procedures that would improve the performance of the breadth first search heuristic in finding the minimum connected dominating set D."]},{"key":"dc:title","label":"Title","values":["Connected Domination in Graphs"]}]}],"canonical_facts":{"dc:contributor":["Stephen Suen, Ph.D.","Natasha Jonoska, Ph.D.","Gregory McColm, Ph.D."],"dc:creator":["Mahalingam, Gayathri"],"dc:date":["2005-01-01T08:00:00Z"],"dc:description":["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 hDi induced by the set D is connected. The connected domination number γc(G) 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. We present the breadth first search algorithm as a heuristic for finding a connected dominating set whose cardinality is hopefully close to that of a minimum connected dominating set. The algorithm finds a spanning tree T of the graph G = (V, E) using breadth first search, and picks up the non-leaf nodes as the connected dominating set D. There are graphs for which the Breadth first search heuristic does not work so well. We implemented some local optimization procedures that would improve the performance of the breadth first search heuristic in finding the minimum connected dominating set D."],"dc:identifier":["https://digitalcommons.usf.edu/etd/2961"],"dc:language":["EN-US"],"dc:rights.license":["default"],"dc:subject":["Connected dominating set","Algorithms","Breadth first search","Random graphs","Local optimization","American Studies","Arts and Humanities"],"dc:title":["Connected Domination in Graphs"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Thesis","M.A."],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:35:14Z"}