Article ID Journal Published Year Pages File Type
4651311 Discrete Mathematics 2006 14 Pages PDF
Abstract

Broadcast domination was introduced by Erwin in 2002, and it is a variant of the standard dominating set problem, such that different vertices can be assigned different domination powers. Broadcast domination assigns an integer power f(v)⩾0f(v)⩾0 to each vertex vv of a given graph, such that every vertex of the graph is within distance f(v)f(v) from some vertex vv having f(v)⩾1f(v)⩾1. The optimal broadcast domination problem seeks to minimize the sum of the powers assigned to the vertices of the graph. Since the presentation of this problem its computational complexity has been open, and the general belief has been that it might be NP-hard. In this paper, we show that optimal broadcast domination is actually in PP, and we give a polynomial time algorithm for solving the problem on arbitrary graphs, using a non-standard approach.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,