#### Date of Award

5-2007

#### Document Type

Thesis

#### Degree Name

Master of Science (MS)

#### Legacy Department

Computer Science

#### 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.

http://tigerprints.clemson.edu/all_theses/128