A simple linear time algorithm for computing a (2k-1)-spanner of O( n1+ 1/k) size in weighted graphs

Baswana, Surender ; Sen, Sandeep (2007) A simple linear time algorithm for computing a (2k-1)-spanner of O( n1+ 1/k) size in weighted graphs Random Structures and Algorithms, 30 (4). 532- 563. ISSN 1042-9832

PDF - Author Version

Official URL: http://onlinelibrary.wiley.com/doi/10.1002/rsa.201...

Related URL: http://dx.doi.org/10.1002/rsa.20130


Let G = (V,E) be an undirected weighted graph on |V | = n vertices and |E| = m edges. A t-spanner of the graph G, for any t ≥ 1, is a subgraph G(V,ES), ES such that the distance between any pair of vertices in the subgraph is at most t times the distance between them in the graph G. Computing a t-spanner of minimum size (number of edges) has been a widely studied and well-motivated problem in computer science. In this paper we present the first linear time randomized algorithm that computes a t-spanner of a given weighted graph. Moreover, the size of the t-spanner computed essentially matches the worst case lower bound implied by a 43-year old girth lower bound conjecture made independently by Erdos, Bollobàs, and Bondy & Simonovits. Our algorithm uses a novel clustering approach that avoids any distance computation altogether. This feature is somewhat surprising since all the previously existing algorithms employ computation of some sort of local or global distance information, which involves growing either breadth first search trees up to θ(t)-levels or full shortest path trees on a large fraction of vertices. The truly local approach of our algorithm also leads to equally simple and efficient algorithms for computing spanners in other important computational environments like distributed, parallel, and external memory.

Item Type:Article
Source:Copyright of this article belongs to John Wiley and Sons.
ID Code:90259
Deposited On:08 May 2012 14:36
Last Modified:19 May 2016 04:31

Repository Staff Only: item control page