Sammanfattning av denna webbsida: I alla par problem med flaskhalsar (APBP) får man en riktad graf med riktiga vikter på kanterna. Betrakta vikterna som kapacitet, uppmanas man att bestämma, för alla par (s,t) av hörn, den maximala mängden flöde som kan dirigeras längs en enda väg från s till t. APBP problemet studerades först i verksamheten forskning, kort efter införandet av maximal flöden och alla par kortaste vägar. Vi presenterar den första verkligt subkubiska algoritmen för APBP i allmänna täta grafer. I synnerhet, vi ger ett förfarande för att beräkna (max, min)-produkten av två godtyckliga matriser över R  på {∞, −∞} i O(n 2+./3 ) ≤ O(n 2.792 ) tid, där n är antalet hörn och  på är exponenten för matris multiplikation över ringar. Max-min produkter kan användas för att beräkna de maximala flaskhalsvärden för alla par hörn tillsammans med en "framgångsmatris" från vilken man kan extrahera en explicit maximal flaskhals väg för varje par hörn i tid linjär i längden på vägen.
Den första verkligt subkubiska algoritmen för Min-Max Product gavs av Vassilevska et al. REF, som förbättrades till tiden O(n) +3
All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time
{'venue': 'Theory of Computing', 'journal': 'Theory of Computing', 'mag_field_of_study': ['Mathematics', 'Computer Science']}