Maximum Local Edge Connectivity (Maximum Flow)

From Algorithm Wiki
Jump to navigation Jump to search

Description

Find the pair of nodes with the maximum number of edge-disjoint paths between them

Related Problems

Related: st-Maximum Flow, Integer Maximum Flow, Unweighted Maximum Flow, Non-integer Maximum Flow, Minimum-Cost Flow, All-Pairs Maximum Flow

Parameters

$V$: number of vertices

$E$: number of edges

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Ford & Fulkerson 1955 $O(E^{2}U)$ $O(E)$ Exact Deterministic Time & Space
Dinitz 1970 $O(V^{2}E)$ $O(E)$ Exact Deterministic Time & Space
Edmonds & Karp 1972 $O(E^{2} \log U)$ $O(E)$ Exact Deterministic Time & Space
Karzanov 1974 $O(V^{3})$ $O(V^{2})$ Exact Deterministic Time & Space
Galil & Naamad 1980 $O(VE \log^{2} V)$ $O(E)$ Exact Deterministic Time & Space
Dantzig 1951 $O(V^{2}EU)$ $O(VE)$? Exact Deterministic
Dinitz (with dynamic trees) 1973 $O(VE \log U)$ $O(E)$ Exact Deterministic Time
Cherkassky 1977 $O(V^{2}E^{0.5})$ $O(E)$ Exact Deterministic Time & Space
Sleator & Tarjan 1983 $O(VE \log V)$ $O(E)$ Exact Deterministic Time
Goldberg & Tarjan 1986 $O(VE \log (V^{2}/E))$ $O(E)$ Exact Deterministic Time
Ahuja & Orlin 1987 $O(VE + V^{2} \log U)$ $O(ELogU)$ Exact Deterministic Time
Ahuja et al. 1987 $O(VELog(V(LogU)$^{0.5} / E)) Exact Deterministic Time
MKM Algorithm 1978 $O(V^{3})$ $O(E)$ Exact Deterministic Time & Space
Galil 1978 $O(V^({5}/{3})$E^({2}/{3})) $O(E)$ Exact Deterministic Time & Space
Shiloach 1981 $O(V^{3}*log(V)$/p) $O(E)$ Exact Parallel Time
Gabow 1985 $O(VE*logU)$ $O(E)$ Exact Deterministic Time
Lee, Sidford 2014 $O(E*sqrt(V)$*log^{2}(U)*polylog(E, V, log(U)) $O(E)$ Exact Deterministic Time
Madry 2016 $O(E^({10}/{7})$U^({1}/{7})polylog(V, E, log U)) $O(E)$ Exact Deterministic Time
Kathuria, Liu, Sidford 2020 $O(E^({1}+o({1})$)/sqrt(eps)) $O(E)$ or $O(V^{2})$ ? 1+eps Deterministic Time
Kathuria, Liu, Sidford 2020 $O(E^({4}/{3}+o({1})$)U^({1}/{3})) $O(E)$ or $O(V^{2})$ ? Exact Deterministic Time
Brand et al 2021 $O((E+V^{1.5})$log(U)polylog(V, E, log U)) $O(E)$ Exact Randomized Time
Gao, Liu, Peng 2021 $O(E^({3}/{2}-{1}/{328})$*log(U)*polylog(E)) $O(E)$ Exact Deterministic Time
Chen et al 2022 $O(E^({1}+o({1})$)*log(U)) $O(E)$ Exact Deterministic Time

Reductions FROM Problem

Problem Implication Year Citation Reduction
MAX-CNF-SAT assume: SETH
then: for any $\epsilon > {0}$, in graphs with $n$ nodes and $\tilde{O}(n)$ edges, target cannot be solved in time $O(n^{2-\epsilon})$
2018 https://dl.acm.org/doi/abs/10.1145/3212510 link

References/Citation

https://dl.acm.org/doi/abs/10.1145/3212510