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 -