𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs

✍ Scribed by Elisabeth Gassner; Johannes Hatzl

Publisher
Springer Vienna
Year
2008
Tongue
English
Weight
268 KB
Volume
82
Category
Article
ISSN
0010-485X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Weighted connected domination and Steine
Weighted connected domination and Steiner trees in distance-hereditary graphs
✍ Yeh Hong-Gwa; Gerard J. Chang πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 649 KB

Distance-hereditary graphs are graphs in which every two vertices have the same distance in every connected induced subgraph containing them. This paper studies distance-hereditary graphs from an algorithmic viewpoint. In particular, we present linear-time algorithms for finding a minimum weighted c

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

Domination in planar graphs with small d
Domination in planar graphs with small diameter
✍ Wayne Goddard; Michael A. Henning πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 199 KB

## Abstract MacGillivray and Seyffarth (J Graph Theory 22 (1996), 213–229) proved that planar graphs of diameter two have domination number at most three and planar graphs of diameter three have domination number at most ten. They also give examples of planar graphs of diameter four having arbitrar