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.

Share

COinS