Хронологическая таблица достижений в решении задачи о максимальном потоке
Хронологическая таблица достижений в решении задачи о максимальном
потоке
Хронологическая таблица достижений в решении задачи о максимальном
потоке.[1]
Год
Автор
Оценка
1951
Dantzig
O(n2mU)
1956
Ford & Fulkerson
O(nmU)
1970
EdmondsandKarp
O(nm2)
1970
Dinic
O(n2m)
1972
Edmonds and Karp
O(m2LogU)
1973
Diniс
Gabow
O(nmLogU)
1974
Karzanov
O(n3)
1977
Cherkasky
O(n2m1/2)
1978
Malhotra, Pramodh Kumar, and Maheshwari
O(n3)
1978
Galil
O(n5/3m2/3)
1978
Galil& Naamad
Shiloach
O(nmLog2n)
1980
Sleator and Tarjan
O(nmLogn)
1982
Shiloach& Vishkin
O(n3)
1984
Tarjan
O(n3)
1985
Goldberg
O(n3)
1986
Goldberg &Tarjan
O(nmLog(n2/m))
1987
Ahuja and
Orlin
O(nm + n2LogU)
1987
Ahuja et
al.
O(nmLog(n(Log1/2U)/m))
1989
Cheriyan, Hagerup & Mehlhorn
E(nm + n2Log2n)
1990
Cheriyan
et al.
O(n3/logn)
1990
Alon
O(nm + n8/3Logn)
1992
King, Rao & Tarjan
O(nm + n2+e)
1993
Phillips
& Westbrook
O(nm(Logm/(Logn)n))
1997
Goldberg & Rao
O(min{n2/3,n1/2}m Log(n2/m)LogU)
[1]U – наибольшая величина максимальной
пропускной способности сети (оценки, содержащие U, являются слабо полиномиальными); под E() понимается высокая
вероятность такой оценки (для алгоритмов, допускающих случайное поведение); n – кол-во вершин, m – кол-во рёбер.
