✦ LIBER ✦

Homogeneous sets and domination: A linear time algorithm for distance—hereditary graphs

✍ Scribed by Falk Nicolai; Thomas Szymczak

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 210 KB
Volume: 37
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.1

No coin nor oath required. For personal study only.

📜 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 broadcast do

A linear-time algorithm for broadcast domination in a tree

✍ John Dabney; Brian C. Dean; Stephen T. Hedetniemi 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 268 KB

## 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