A linear-time algorithm for broadcast domination in a tree

A linear-time algorithm for broadcast domination in a tree

0.00 Avg rating0 Votes
Article ID: iaor200969361
Country: United States
Volume: 53
Issue: 2
Start Page Number: 160
End Page Number: 169
Publication Date: Mar 2009
Journal: Networks
Authors: , ,
Keywords: networks
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 (broadcasting to) 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 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. Blair et al. (2004) gave an O(n2) algorithm for trees. In this article, we provide an O(n) algorithm for trees. Our algorithm is notable due to the fact that it makes decisions for each vertex v based on nonlocal information from vertices far away from v, whereas almost all other linear-time algorithms for trees only make use of local information.

Reviews

Required fields are marked *. Your email address will not be published.