TY - GEN

T1 - Generating sparse 2—Spanners

AU - Kortsarz, Guy

AU - Peleg, David

N1 - Funding Information:
*Department of Applied Mathematics and Computer Science, The Weizmmm Institute, Rehovot 76100, Israel. tSupported in part by a Walter and Elise Haas Career Development Award and by a grant from the Basic Research Foundation.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.

PY - 1992

Y1 - 1992

N2 - A k- spanner of a connected graph G=(V, E) is a subgraph G' 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' 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|).

AB - A k- spanner of a connected graph G=(V, E) is a subgraph G' 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' 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|).

UR - http://www.scopus.com/inward/record.url?scp=85030534935&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85030534935&partnerID=8YFLogxK

U2 - 10.1007/3-540-55706-7_7

DO - 10.1007/3-540-55706-7_7

M3 - Conference contribution

AN - SCOPUS:85030534935

SN - 9783540557067

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 73

EP - 82

BT - Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings

A2 - Nurmi, Otto

A2 - Ukkonen, Esko

PB - Springer Verlag

T2 - 3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992

Y2 - 8 July 1992 through 10 July 1992

ER -