On sparse spanners of weighted graphs

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

Research output: Contribution to journalArticle

363 Scopus citations

Abstract

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
Volume9
Issue number1
DOIs
StatePublished - Dec 1 1993

All Science Journal Classification (ASJC) codes

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

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

  • Cite this