A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs

摘要

Let G = (V E) be an undirected weighted graph on vertical bar V vertical bar n vertices and vertical bar E vertical bar = nt edges. A t-spanner of the graph G, for any t >= 1, is a subgraph (V, Es), Es E, 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, Bollobds, 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 theta (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 sparmers in other important computational environments like distributed, parallel, and external memory. (c) 2006 Wiley Periodicals, Inc.