On sparse spanners of weighted graphs

Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, José Soares

Research output: Contribution to journalArticlepeer-review

488 Scopus citations


Given a graph G, a subgraph G' is a t-spanner of G if, for every u, v e{open}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 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)
Pages (from-to)81-100
Number of pages20
JournalDiscrete & Computational Geometry
Issue number1
StatePublished - Dec 1993

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


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

Cite this