Generating sparse spanners for weighted graphs

Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph

Research output: Chapter in Book/Report/Conference proceedingConference contribution

38 Scopus citations


Given a graph G, a subgraph G’ is a it-spanner of G, if for every u, v ∊ V, the distance from u to v in G’ 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.

Original languageEnglish (US)
Title of host publicationSWAT 1990 - 2nd Scandinavian Workshop on Algorithm Theory, Proceedings
EditorsRolf Karlsson, John R. Gilbert
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540528463
StatePublished - 1990
Event2nd Scandinavian Workshop on Algorithm Theory, SWAT 1990 - Bergen, Norway
Duration: Jul 11 1990Jul 14 1990

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume447 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other2nd Scandinavian Workshop on Algorithm Theory, SWAT 1990

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Generating sparse spanners for weighted graphs'. Together they form a unique fingerprint.

Cite this