### 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 language | English (US) |
---|---|

Title of host publication | SWAT 1990 - 2nd Scandinavian Workshop on Algorithm Theory, Proceedings |

Editors | Rolf Karlsson, John R. Gilbert |

Publisher | Springer Verlag |

Pages | 26-37 |

Number of pages | 12 |

ISBN (Print) | 9783540528463 |

DOIs | |

State | Published - Jan 1 1990 |

Event | 2nd Scandinavian Workshop on Algorithm Theory, SWAT 1990 - Bergen, Norway Duration: Jul 11 1990 → Jul 14 1990 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 447 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 2nd Scandinavian Workshop on Algorithm Theory, SWAT 1990 |
---|---|

Country | Norway |

City | Bergen |

Period | 7/11/90 → 7/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