12
$\begingroup$

I am looking for a good reference for bottleneck shortest paths. Specifically, given vertices s and t in an undirected graph with edge weights, you want the shortest path from s to t, where the length of a path is the maximum edge on that path. This can be solved in O(n+m) time by finding the median edge weight and (carefully) recursively deleting half the edges.

Does anyone know a reference for this?

$\endgroup$
  • $\begingroup$ Perhaps this is a moot point, but the problem you describe is the minimax path problem. Bottleneck shortest path is the max-min version of what you describe. An algorithm for one of the version generally (always?) yields an algorithm for the other version however. $\endgroup$ – bbejot May 12 '11 at 3:39
10
$\begingroup$

P. M. Camerini (1978), The min-max spanning tree problem and some extensions, Information Processing Letters 7 (1): 10–14, doi:10.1016/0020-0190(78)90030-3

$\endgroup$
  • 5
    $\begingroup$ Btw, if you want to solve the single-source (and in a sense the all-pairs) version of the problem for undirected graphs, you can do it in randomized O(m+n) time: T.C. Hu noted in 1961 that the bottleneck paths for all pairs are encoded in a max spanning tree; then Karger,Klein and Tarjan's linear time min spanning tree algorithm gives you what you want. $\endgroup$ – virgi Feb 28 '11 at 1:54
  • $\begingroup$ As far as I can tell the reference is not what I need. An st path in a min-max spanning tree is not necessaryily a bottleneck shortest st path. Also, the KKT linear expected time algorithm is not what I need either, since I want deterministic not expected running time. Thanks anyway for the help though. $\endgroup$ – Ben Mar 5 '11 at 21:55
  • 4
    $\begingroup$ Actually, the st path P in a minimum spanning tree T has a minimum maximum edge weight over all st paths. Suppose it doesn't. Then let the max edge of P be e. Removing e from T creates a cut of the graph. The real minmax st path P' must have an edge e' crossing this cut. Adding e' to T\{e} creates a new spanning tree T' which must have a smaller cost than T since the weight of e' is at most the max edge weight on P' which is less than w(e). This contradicts the fact that T is a min spanning tree. $\endgroup$ – virgi May 12 '11 at 17:02
2
$\begingroup$

On the Bottleneck Shortest Path Problem

$\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.