Date of Award
5-2007
Document Type
Thesis
Degree Name
Master of Science (MS)
Committee Chair/Advisor
Dean, Brian C
Abstract
The broadcast domination problem is a variant of the classical minimum dominating set problem in which a transmitter of power p at vertex v is capable of dominating all vertices within distance p from v. Our goal is to assign a broadcast power f(v) to every vertex v in a graph such that the sum for all v over V of f(v) is minimized, and such that every vertex u with f(u) = 0 is within distance f(v) of some vertex v with f(v) > 0. The problem is solvable in polynomial time on a general graph, and Blair et al. gave an O(n^2) algorithm for trees. We provide an O(n) algorithm for trees. Our algorithm is notable because it makes decisions for each vertex v based on 'non-local' information from vertices far away from v, whereas almost all other linear-time algorithms for trees only make use of local information.
Recommended Citation
Dabney, John, "A LINEAR-TIME ALGORITHM FOR BROADCAST DOMINATION IN A TREE" (2007). All Theses. 128.
https://open.clemson.edu/all_theses/128