@inproceedings{5e07f8e9431a425db4603c8433bea8cc,

title = "Generating sparse spanners for weighted graphs",

abstract = "Given a graph G, a subgraph G{\textquoteright} is a it-spanner of G, if for every u, v ∊ V, the distance from u to v in G{\textquoteright} is at most t times longer than the distance in G. In this paper we give a very simple algorithm for constructing sparse spanners for arbitrary weighted graphs. We then apply this algorithm to obtain specific results for planar graphs and Euclidean graphs. We discuss the optimality of our results and present several nearly matching lower bounds.",

author = "Ingo Alth{\"o}fer and Gautam Das and David Dobkin and Deborah Joseph",

note = "Funding Information: t The work of the second and fourth authors was supported by NSF PYI grant DCR-8402375. The work of the third author was supported by NSF grant CCI%-8700917.; 2nd Scandinavian Workshop on Algorithm Theory, SWAT 1990 ; Conference date: 11-07-1990 Through 14-07-1990",

year = "1990",

doi = "10.1007/3-540-52846-6_75",

language = "English (US)",

isbn = "9783540528463",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "26--37",

editor = "Rolf Karlsson and Gilbert, {John R.}",

booktitle = "SWAT 1990 - 2nd Scandinavian Workshop on Algorithm Theory, Proceedings",

address = "Germany",

}