1
$\begingroup$

I was wondering what is the most efficient way to find the shortest distances between all pairs of vertices in a graph where the shortest path between those vertices has length $\geq L$. The only way I know of so far is to choose a smaller "hitting set" $B$ such that each long shortest path contains at least one node from $B$ with high probability. Then you can find all distances from nodes in $B$ to all nodes in the graph, and get $d(u, v) = \min_b d(u, b) + d(b, v)$.

Are there any faster methods?

Thanks!

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ What does "with high probability" mean? Is your algorithm randomized? $\endgroup$
    – Jeffε
    May 3, 2014 at 0:58
  • $\begingroup$ Yep, that algorithm is randomized. $\endgroup$
    – Jessica
    May 3, 2014 at 7:51

1 Answer 1

Reset to default
2
$\begingroup$

If you accept approximations to the distances, you can take a look at distance oracles. A good source is the paper on distance oracles by Thorup-Zwick, Approximate Distance Oracles (STOC 2001).

Distance oracles can offer constant (but approximate) look-up.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.