Baswana, Surender ; Sen, Sandeep (2007) A simple linear time algorithm for computing a (2k1)spanner of O( n^{1+ 1/k}) size in weighted graphs Random Structures and Algorithms, 30 (4). 532 563. ISSN 10429832

PDF
 Author Version
293kB 
Official URL: http://onlinelibrary.wiley.com/doi/10.1002/rsa.201...
Related URL: http://dx.doi.org/10.1002/rsa.20130
Abstract
Let G = (V,E) be an undirected weighted graph on V  = n vertices and E = m edges. A tspanner of the graph G, for any t ≥ 1, is a subgraph G(V,E_{S}), E_{S} 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 tspanner of minimum size (number of edges) has been a widely studied and wellmotivated problem in computer science. In this paper we present the first linear time randomized algorithm that computes a tspanner of a given weighted graph. Moreover, the size of the tspanner computed essentially matches the worst case lower bound implied by a 43year 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