Faster algorithms for all-pairs small stretch distances in weighted graphs


Autoria(s): Kavitha, Telikepalli
Data(s)

2007

Resumo

Abstract. Let G = (V,E) be a weighted undirected graph, with non-negative edge weights. We consider the problem of efficiently computing approximate distances between all pairs of vertices in G. While many efficient algorithms are known for this problem in unweighted graphs, not many results are known for this problem in weighted graphs. Zwick [14] showed that for any fixed ε> 0, stretch 1 1 + ε distances between all pairs of vertices in a weighted directed graph on n vertices can be computed in Õ(n ω) time, where ω < 2.376 is the exponent of matrix multiplication and n is the number of vertices. It is known that finding distances of stretch less than 2 between all pairs of vertices in G is at least as hard as Boolean matrix multiplication of two n×n matrices. It is also known that all-pairs stretch 3 distances can be computed in Õ(n 2) time and all-pairs stretch 7/3 distances can be computed in Õ(n 7/3) time. Here we consider efficient algorithms for the problem of computing all-pairs stretch (2+ε) distances in G, for any 0 < ε < 1. We show that all pairs stretch (2 + ε) distances for any fixed ε> 0 in G can be computed in expected time O(n 9/4 logn). This algorithm uses a fast rectangular matrix multiplication subroutine. We also present a combinatorial algorithm (that is, it does not use fast matrix multiplication) with expected running time O(n 9/4) for computing all-pairs stretch 5/2 distances in G. 1

Formato

application/pdf

Identificador

http://eprints.iisc.ernet.in/41497/1/10.1.1.100.8606.pdf

Kavitha, Telikepalli (2007) Faster algorithms for all-pairs small stretch distances in weighted graphs. In: Proceedings of Foundations of Software Software Technology and Theoretical Computer Science FSTTCS 2007.

Relação

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.8606

http://eprints.iisc.ernet.in/41497/

Palavras-Chave #Computer Science & Automation (Formerly, School of Automation)
Tipo

Conference Paper

PeerReviewed