Cheriyan & Hagerup (st-Maximum Flow Maximum Flow)
Jump to navigation
Jump to search
Time Complexity
$O(VE \log V)$
Space Complexity
$O(V + E)$ words
(Derived: d_heap and e_heap are size O(V). Adjacency list of a given vertex is O(V). Dynamic trees data structure is size O(E).)
Description
Push-relabel method
Approximate?
Exact
Randomized?
Yes, Las Vegas
Model of Computation
Word RAM
Year
1989