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
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.