2004-45: A Computational Study of the Broadcast Domination Problem

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