## DIMACS TR: 2004-45

##
A Computational Study of the Broadcast Domination Problem

### Authors: Steven B. Horton, Claudio N. Meneses, Arup Mukherjee and M. Erol Ulucakli

**
ABSTRACT
**
The Broadcast Domination problem seeks a function $f:V \rightarrow \{0,1,2, \dot
s \}$ that minimizes $\sum_{v \in V} f(v)$ with the constraint that for every $v
$ with $f(v)=0$, there is a vertex $u \in V$ with $f(u)$ at least the distance f
rom $u$ to $v$ in $G$. This is a generalization of the standard Dominating Set
problem. This note investigates the problem from a computational standpoint.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-45.ps.gz

DIMACS Home Page