Theory of Computing
-------------------
Title     : All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time
Authors   : Virginia Vassilevska, R. Ryan Williams, and Raphael Yuster
Volume    : 5
Number    : 9
Pages     : 173-189
URL       : https://theoryofcomputing.org/articles/v005a009

Abstract
--------

In the "all pairs bottleneck paths" (APBP) problem, one 
is given a directed graph with real weights on its edges.  
Viewing the weights as capacities, one is asked to determine, 
for all pairs (s, t) of vertices, the maximum amount of flow
which can be routed along a single path from  s  to  t.  The 
APBP problem was first studied in operations research, shortly
after the introduction of maximum flows and all pairs shortest 
paths.

We present the first truly subcubic algorithm for APBP in 
general dense graphs. In particular, we give a procedure for 
computing the  (max, min)-product of two arbitrary matrices 
over   R u (infty, -infty)  in 
O(n^{2+omega/3}) < O(n^2.792)  time, where n  is the number of 
vertices and  omega  is the exponent for matrix multiplication
over rings.   Max-min products can be used to compute the maximum 
bottleneck values for all pairs of vertices together with a 
"successor matrix" from which one can extract an explicit maximum 
bottleneck path for any pair of vertices in time linear in the
length of the path.