𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A linear-time algorithm for broadcast domination in a tree

✍ Scribed by John Dabney; Brian C. Dean; Stephen T. Hedetniemi

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
268 KB
Volume
53
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

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 Ξ£~v__Ξ΅__V~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 (Heggernes and Lokshtanov, Disc Math (2006), 3267–3280) and Blair et al. (Congr. Num. (2004), 55–77.) gave an O(n^2^) 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. Β© 2008 Wiley Periodicals, Inc. NETWORKS, 2009

πŸ“œ SIMILAR VOLUMES

A linear-time algorithm for connectedr-d
A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
✍ BrandstοΏ½dt, Andreas; Dragan, Feodor F. πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 83 KB πŸ‘ 1 views

A distance-hereditary graph is a connected graph in which every induced path is isometric, i.e., the distance of any two vertices in an induced path equals their distance in the graph. We present a linear time labeling algorithm for the minimum cardinality connected r-dominating set and Steiner tree

A Linear Time Algorithm for Finding ak-T
A Linear Time Algorithm for Finding ak-Tree Core
✍ Akiyoshi Shioura; Takeaki Uno πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 173 KB

Given a tree containing n vertices, consider the sum of the distance between all Ε½ . vertices and a k-leaf subtree subtree which contains exactly k leaves . A k-tree core is a k-leaf subtree which minimizes the sum of the distances. In this paper, we propose a linear time algorithm for finding a k-t