✦ LIBER ✦

A Note on Distance Approximating Trees in Graphs

✍ Scribed by Victor Chepoi; Feodor Dragan

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 126 KB
Volume: 21
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1999.0381

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

Approximating Steiner trees in graphs wi

Approximating Steiner trees in graphs with restricted weights

✍ Halld�rsson, Magn�s M.; Ueno, Shuichi; Nakao, Hiroshi; Kajitani, Yoji 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB 👁 2 views

We analyze the approximation ratio of the average distance heuristic for the Steiner tree problem on graphs and prove nearly tight bounds for the cases of complete graphs with binary weights {1, d} or weights in the interval [1, d], where d °2. The improvement over other analyzed algorithms is a fac

A note on graphs with diameter-preservin

A note on graphs with diameter-preserving spanning trees

✍ Fred Buckley; Martin Lewinter 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB 👁 1 views

The distance between a pair of vertices u, u in a graph G is the length of a shortest path joining u and u. The diameter diam(G) of G is the maximum distance between all pairs of vertices in G. A spanning tree Tof G is diameter preserving if diam(T) = diam(G). In this note, we characterize graphs th

A note on conservative graphs

✍ Arthur T. White 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract An application of conservative graphs to topological graph theory is indicated.

A note on coset graphs

✍ Ulrike Baumann 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

## Abstract Coset graphs are a generalization of Cayley graphs. They arise in the construction of graphs and digraphs with transitive automorphism groups. Moreover, the consideration of coset graphs makes it possible to give an algebraic description of regular connected graphs of even degree. In th

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