Header menu link for other important links
Approximating shortest paths in graphs
Published in
Volume: 5431 LNCS
Pages: 32 - 43
Computing all-pairs distances in a graph is a fundamental problem of computer science but there has been a status quo with respect to the general problem of weighted directed graphs. In contrast, there has been a growing interest in the area of algorithms for approximate shortest paths leading to many interesting variations of the original problem. In this article, we trace some of the fundamental developments like spanners and distance oracles, their underlying constructions, as well as their applications to the approximate all-pairs shortest paths. © Springer-Verlag Berlin Heidelberg 2009.
About the journal
Published in
Open Access
Impact factor