On sparse spanners of weighted graphs

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

doi:10.1007/BF02189308

On sparse spanners of weighted graphs

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

Research output: Contribution to journal › Article › peer-review

494 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 language	English (US)
Pages (from-to)	81-100
Number of pages	20
Journal	Discrete & Computational Geometry
Volume	9
Issue number	1
DOIs	https://doi.org/10.1007/BF02189308
State	Published - Dec 1993

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1007/BF02189308

Cite this

@article{73adf5f1d9ca469a99980479a21d4614,

title = "On sparse spanners of weighted graphs",

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.",

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

year = "1993",

month = dec,

doi = "10.1007/BF02189308",

language = "English (US)",

volume = "9",

pages = "81--100",

journal = "Discrete & Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - On sparse spanners of weighted graphs

AU - Althöfer, Ingo

AU - Das, Gautam

AU - Dobkin, David

AU - Joseph, Deborah

AU - Soares, José

PY - 1993/12

Y1 - 1993/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0039227987&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0039227987&partnerID=8YFLogxK

U2 - 10.1007/BF02189308

DO - 10.1007/BF02189308

M3 - Article

AN - SCOPUS:0039227987

SN - 0179-5376

VL - 9

SP - 81

EP - 100

JO - Discrete & Computational Geometry

JF - Discrete & Computational Geometry

IS - 1

ER -

On sparse spanners of weighted graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this