✦ LIBER ✦

Generating Sparse 2-Spanners

✍ Scribed by G. Kortsarz; D. Peleg

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 510 KB
Volume: 17
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1994.1032

No coin nor oath required. For personal study only.

✦ Synopsis

A (k)-spanner of a connected graph (G=(V, E)) is a subgraph (G^{\prime}) consisting of all the vertices of (V) and a subset of the edges, with the additional property that the distance between any two vertices in (G^{\prime}) is larger than that distance in (G) by no more than a factor of (k). This note concerns the problem of finding the sparsest 2 -spanner in a given graph and presents an approximation algorithm for this problem with approximation ratio (\log (|E| /|V|)). (1) 1994 Academic Press, Inc.

📜 SIMILAR VOLUMES

Small Hop-diameter Sparse Spanners for D

Small Hop-diameter Sparse Spanners for Doubling Metrics

✍ T.-H. Hubert Chan; Anupam Gupta 📂 Article 📅 2008 🏛 Springer 🌐 English ⚖ 363 KB

Constructing sparse spanners for most gr

Constructing sparse spanners for most graphs in higher dimensions

✍ Barun Chandra 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 444 KB

Grid spanners

✍ Arthur L. Liestman; Thomas C. Shermer 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 837 KB

Graph spanners

✍ David Peleg; Alejandro A. Schäffer 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 816 KB

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 classe

Sparse generalized Fourier transforms

✍ Krister Åhlander; Daniel Henriksson 📂 Article 📅 2007 🏛 Springer Netherlands 🌐 English ⚖ 824 KB

Network flow spanners

✍ Feodor F. Dragan; Chenyu Yan 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB