Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs
share
In a directed graph G=(V,E) with a capacity on every edge, a bottleneck path (or widest path) between two vertices is a path maximizing the minimum capacity of edges in the path. For the single-source all-destination version of this problem in directed graphs, the previous best algorithm runs in O(m+n n) (m=|E| and n=|V|) time, by Dijkstra search with Fibonacci heap [Fredman and Tarjan 1987]. We improve this time bound to O(m√( n)), thus it is the first algorithm which breaks the time bound of classic Fibonacci heap when m=o(n√( n)). It is a Las-Vegas randomized approach. By contrast, the s-t bottleneck path has an algorithm with running time O(mβ(m,n)) [Chechik et al. 2016], where β(m,n)={k≥ 1: ^(k)n≤m/n}.
READ FULL TEXT