@inproceedings{99ebb1c5b5fd4a6eb5115a77ad23ae06,
title = "Generating sparse 2—Spanners",
abstract = "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|).",
author = "Guy Kortsarz and David Peleg",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1992.; 3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992 ; Conference date: 08-07-1992 Through 10-07-1992",
year = "1992",
doi = "10.1007/3-540-55706-7\_7",
language = "American English",
isbn = "9783540557067",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "73--82",
editor = "Otto Nurmi and Esko Ukkonen",
booktitle = "Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings",
address = "Germany",
}