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!

$\endgroup$
  • 2
    $\begingroup$ What does "with high probability" mean? Is your algorithm randomized? $\endgroup$ – Jeffε May 3 '14 at 0:58
  • $\begingroup$ Yep, that algorithm is randomized. $\endgroup$ – Jessica May 3 '14 at 7:51
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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