✦ LIBER ✦

A note on distance approximating trees in graphs

✍ Scribed by V. Chepoi; F. Dragan

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 12 KB
Volume: 3
Category: Article
ISSN: 1571-0653
DOI: 10.1016/s1571-0653(05)80019-8

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A Note on Distance Approximating Trees i

A Note on Distance Approximating Trees in Graphs

✍ Victor Chepoi; Feodor Dragan 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 126 KB

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 approximating graph genus

✍ Jianer Chen; Saroja P. Kanchi; Arkady Kanevsky 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 551 KB

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 distance matrices with unicycl

A note on distance matrices with unicyclic graph realizations

✍ J.M.S Simões-Pereira 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 643 KB

We give necessary and sufficient conditions for a distance matrix to have a unicycfic graph as unique optimal graph realization.