Back to Search
Start Over
Fast deterministic distributed algorithms for sparse spanners
- Source :
-
Theoretical Computer Science . Jun2008, Vol. 399 Issue 1/2, p83-100. 18p. - Publication Year :
- 2008
-
Abstract
- Abstract: This paper concerns the efficient construction of sparse and low stretch spanners for unweighted arbitrary graphs with nodes. All previous deterministic distributed algorithms, for constant stretch spanners of edges, have a running time for some constant depending on the stretch. Our deterministic distributed algorithms construct constant stretch spanners of edges in time for any constant . More precisely, in Linial’s free model a.k.a model, we construct in time, for every graph, a -spanner of edges, i.e., a spanning subgraph in which the distance is at most 3 times the distance of the original graph plus 2. The result is extended to -spanners with edges for every integer parameter , where . If the minimum degree of the graph is , then, in the same time complexity, a -spanner with edges can be constructed. [Copyright &y& Elsevier]
- Subjects :
- *ALGORITHMS
*WRENCHES
*COMPUTER science
*SCIENCE
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 399
- Issue :
- 1/2
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 31922582
- Full Text :
- https://doi.org/10.1016/j.tcs.2008.02.019