Sammanfattning Låt G = (V, E, w) vara en riktad graf, där w : V → R är en vikt funktion definieras på dess hörn. Flaskhalsens vikt, eller kapaciteten, hos en stig är den minsta vikten av en vertex på stigen. För två hörn u, v kapaciteten från u till v, betecknad av c (u, v), är den maximala flaskhals vikt av en väg från u till v. I All-Pairs Bottleneck Paths (APBP) problem uppgiften är att hitta kapaciteter för alla beställda par av hörn. Vårt huvudsakliga resultat är en O(n 2.575 ) tid algoritm för APBP. Exponenten är härledd från exponenten för snabb matris multiplikation. En variant av vår algoritm beräknar kortaste vägar av maximal flaskhals vikt. Låt d(u, v) betecknar (oviktat) avstånd från u till v, och låt sc (u, v) betecknar den maximala flaskhals vikten av en väg från u till v med längd d (u, v). All-Pairs Bottleneck Shortest Paths (APBSP) problem är att beräkna sc (u, v) för alla beställda par av hörn. Vi presenterar en algoritm för APBSP vars körtid är O(n 2.86 ).
Shapira m.fl. REF föreslog en O(n 2.575 )-tidsalgoritm för en vertex-viktad variant av APBP.
All-Pairs Bottleneck Paths in Vertex Weighted Graphs
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}