On sparse spanners of weighted graphs |
| |
Authors: | Ingo Althöfer Gautam Das David Dobkin Deborah Joseph José Soares |
| |
Affiliation: | (1) Fakultät für Mathematik, Universität Bielefeld, Postfach 8640, 4800 Bielefeld, Germany;(2) Mathematical Sciences Department, Memphis State University, 38152 Memphis, TN, USA;(3) Department of Computer Science, Princeton University, 08544 Princeton, NJ, USA;(4) Department of Computer Sciences, University of Wisconsin, 53706 Madison, WI, USA;(5) Universidade de São Paulo, IME-USP/MAC, 01498-970 Sao Paolo, SP, Brazil;(6) Department of Computer Science, University of Chicago, 60637 Chicago, IL, USA |
| |
Abstract: | Given a graphG, a subgraphG' is at-spanner ofG if, for everyu,v V, the distance fromu tov inG' is at mostt times longer than the distance inG. 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.The work of G. Das and D. Joseph was supported by NSF PYI Grant DCR-8402375. The work of D. Dobkin was supported by NSF Grant CCR-8700917. The work of J. Soares was supported by CNPq proc 203039/87.4 (Brazil) and NSF Grant CCR-9014562. This research was accomplished while G. Das was a student at the University of Wisconsin-Madison. A preliminary version was presented at the Second Scandinavian Workshop on Algorithm Theory, Bergen, Norway, 1990, under the title Generating Sparse Spanners for Weighted Graphs, and proceedings appear in the series Lecture Notes in Computer Science, Springer-Verlag. The preliminary version also appears as Princeton University Technical Report CS-TR-261-90, and as University of Wisconsin-Madison Computer Sciences Technical Report 882. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|