The algebraic Monge property and path problems

We show how our algorithms can be modified to solve bottleneck shortest path problems, even though strict compatibility does not hold in that case. For example, we give a linear time algorithm for the unrestricted shortest path bottleneck problem on n nodes, also O(kn) and O(n3/2log5/2n) time algorithms for the k-shortest path bottleneck problem.