Back to search

Clemson University

A LINEAR-TIME ALGORITHM FOR BROADCAST DOMINATION IN A TREE

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Dabney, John
Contributors dc:contributor
  • Dean, Brian C

Subjects

dc:subject × 3

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_theses/128

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Dabney, John. A LINEAR-TIME ALGORITHM FOR BROADCAST DOMINATION IN A TREE. Thesis thesis, https://open.clemson.edu/all_theses/128