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?

Improve this question
$\endgroup$
1
  • $\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, 2011 at 3:39

2 Answers 2

Reset to default
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

Improve this answer
$\endgroup$
3
  • 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, 2011 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, 2011 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, 2011 at 17:02
2
$\begingroup$

On the Bottleneck Shortest Path Problem

Improve this answer
$\endgroup$
2

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.