Quick links

Generating Sparse Spanners for Weighted Graphs

Report ID:
TR-261-90
Date:
March 1990
Pages:
13
Download Formats:
[PDF]

Abstract:

Given a graph G, a subgraph G' is a t-spanner of G, if for every u,v that is an element of 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.

Follow us: Facebook Twitter Linkedin