Cheriyan & Hagerup (st-Maximum Flow Maximum Flow)
Revision as of 11:36, 15 February 2023 by Admin (talk | contribs) (Created page with "== 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 == Reference == https://ieeexplore.ieee.org/document/63465")
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