All-Pairs Small-Stretch Paths |
| |
Authors: | Edith Cohen Uri Zwick |
| |
Institution: | AT&T Labs—Research, 180 Park Ave., Room A105, Florham Park, New Jersey, 07932-0971, f1;Department of Computer Science, Tel Aviv University, Tel Aviv, 69978, Israel, f2 |
| |
Abstract: | Let G = (V, E) be a weighted undirected graph. A path between u, v V is said to be of stretch t if its length is at most t times the distance between u and v in the graph. We consider the problem of finding small-stretch paths between all pairs of vertices in the graph G.It is easy to see that finding paths of stretch less than 2 between all pairs of vertices in an undirected graph with n vertices is at least as hard as the Boolean multiplication of two n × n matrices. We describe three algorithms for finding small-stretch paths between all pairs of vertices in a weighted graph with n vertices and m edges. The first algorithm, STRETCH2, runs in Õ(n3/2m1/2) time and finds stretch 2 paths. The second algorithm, STRETCH7/3, runs in Õ(n7/3) time and finds stretch 7/3 paths. Finally, the third algorithm, STRETCH3, runs in Õ(n2) and finds stretch 3 paths.Our algorithms are simpler, more efficient and more accurate than the previously best algorithms for finding small-stretch paths. Unlike all previous algorithms, our algorithms are not based on the construction of sparse spanners or sparse neighborhood covers. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|