All-Pairs Bottleneck Paths in Vertex Weighted Graphs

Let G=(V,E,w) be a directed graph, where w:V→ℝ is a weight function defined on its vertices. The bottleneck weight, or the capacity, of a path is the smallest weight of a vertex on the path. For two vertices u,v the capacity from u to v, denoted by c(u,v), is the maximum bottleneck weight of a path from u to v. In the All-Pairs Bottleneck Paths (APBP) problem the task is to find the capacities for all ordered pairs of vertices. Our main result is an O(n2.575) time algorithm for APBP. The exponent is derived from the exponent of fast matrix multiplication.