(t, r)-Broadcast Domination in Networks

We study a recently introduced generalization of distance domination in graphs known as (t, r)Broadcast Domination: A set S of broadcasting vertices transmit a signal of initial strength t; the strength of the signal decays linearly along edges according to distance, that is, a vertex at a distance d < t from a broadcasting vertex u ∈ S receives a signal of strength t − d, for each u ∈ S. The goal is to determine a set S of broadcasting vertices of minimum size, which ensures that every vertex in the network receives a cumulative signal strength of at least r. In this paper, we initiate the study of the (t, r)-Broadcast Domination problem in general graphs. Our results include a general approximation algorithm and optimal polynomial time algorithms for cographs. Moreover, we consider graphs of bounded Neighborhood diversity (nd), and graphs of bounded Iterated type partition number (itp) and give: (i) a fixed parameter tractable (FPT) algorithm for (t, r)Broadcast Domination parameterized by nd; (ii) a FPT algorithm for (t, r)-Broadcast Domination parameterized by itp plus the solution size B = |S|; (iii) a FPT algorithm for (t, r)-Broadcast Domination parameterized by itp plus the demand r.