Generating sparse spanners for weighted graphs

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

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

26 Scopus citations

Abstract

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
Pages26-37
Number of pages12
ISBN (Print)9783540528463
DOIs
StatePublished - Jan 1 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

Other

Other2nd Scandinavian Workshop on Algorithm Theory, SWAT 1990
CountryNorway
CityBergen
Period7/11/907/14/90

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Althöfer, I., Das, G., Dobkin, D., & Joseph, D. (1990). Generating sparse spanners for weighted graphs. In R. Karlsson, & J. R. Gilbert (Eds.), SWAT 1990 - 2nd Scandinavian Workshop on Algorithm Theory, Proceedings (pp. 26-37). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 447 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-52846-6_75