✦ LIBER ✦

Graph spanners

✍ Scribed by David Peleg; Alejandro A. Schäffer

Publisher: John Wiley and Sons
Year: 1989
Tongue: English
Weight: 816 KB
Volume: 13
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190130114

No coin nor oath required. For personal study only.

✦ Synopsis

Given a graph G = (V E), a subgraph G' = (V E ' ) is a t-spanner of G if for every u, u E V the distance from u to u in G' is at most t times longer than that distance in G. This paper presents some results concerning the existence and efficient constructability of sparse spanners for various classes of graphs, including general undirected graphs, undirected chordal graphs, and general directed graphs.

📜 SIMILAR VOLUMES

Minimum spanners of butterfly graphs

✍ Shien-Ching Hwang; Gen-Huey Chen 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 251 KB

Euclidean spanner graphs with degree fou

Euclidean spanner graphs with degree four

✍ Jeffrey S. Salowe 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 826 KB

Tree Spanners for Bipartite Graphs and P

Tree Spanners for Bipartite Graphs and Probe Interval Graphs

✍ Andreas Brandstadt; Feodor F. Dragan; Hoang-Oanh Le; Van Bang Le; Ryuhei Uehara 📂 Article 📅 2006 🏛 Springer 🌐 English ⚖ 336 KB

Spanners of de Bruijn and Kautz graphs

✍ Rabah Harbane; Carles Padró 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 530 KB

Optimal tree 3-spanners in directed path

Optimal tree 3-spanners in directed path graphs

✍ Le, Ho�ng-Oanh; Le, Van Bang 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB 👁 2 views

In a graph G, a spanning tree T is called a tree t-spanner of G if the distance between any two vertices in T is at most t times their distance in G. While the complexity of finding a tree t-spanner of a given graph is known for any fixed t 3, the case t ϭ 3 still remains open. In this article, we s

On tree 3-spanners in directed path grap

On tree 3-spanners in directed path graphs

✍ B.S. Panda; Anita Das 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB