𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Doubly chordal graphs, steiner trees, and connected domination

✍ Scribed by M. Moscarini

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
949 KB
Volume
23
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Permutation graphs: Connected domination
Permutation graphs: Connected domination and Steiner trees
✍ Charles J. Colbourn; Lorna K. Stewart πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 702 KB

Efficient algorithms are developed for finding a minimum cardinality connected dominating set and a minimum cardinality Steiner tree in permutation graphs. This contrasts with the known NP-completeness of both problems on comparability graphs in general.

Distance Approximating Trees for Chordal
Distance Approximating Trees for Chordal and Dually Chordal Graphs
✍ Andreas BrandstΓ€dt; Victor Chepoi; Feodor Dragan πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 165 KB

In this paper we show that, for each chordal graph G, there is a tree T such that T is a spanning tree of the square G 2 of G and, for every two vertices, the distance between them in T is not larger than the distance in G plus 2. Moreover, we prove that, if G is a strongly chordal graph or even a d

Tree-decompositions, tree-representabili
Tree-decompositions, tree-representability and chordal graphs
✍ Reinhard Diestel πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 427 KB

The following assertions are shown to be equivalent, for any countable graph G: (1) G can be represented as the intersection graph of a family of subtrees of a tree; (2) G admits a tree-decomposition (Robertson/Seymour) into primes; (3) G is chordal, and G admits a simpkial tree-decomposition (Halin