[Algorithms] Network Flow

Steps

Constraints: restate question requirements
Formulation: (1) draw flow graph, (2) nodes, (3) edges, (4) capacities
Solution: the requirement for the max-flow
Complexity/Algorithm: what algorithm is used + the corresponding complexity
Correctness: restate the formulation with the implications

Terms

Residual Graph: a graph with some flow
Augmenting Path: a path from s to t

Algorithms for Max-Flow

Ford-Fulkerson
– Calculate C = min( {sum of capacity from source}, {sum of capacity to sink} )
– Total complexity: O( ( |V| + |E| ) C )

Scaling Ford-Fulkerson
– Calculate C = {sum of capacity from source}
– Total complexity: O( |E|^2 log C )

Edmonds-Karp
– Total complexity: O( |E|^2 |V| )
– This algorithm’s complexity does not depend on C, and thus the algorithm is strongly polynomial

Preflow-Push
– Total complexity: O(|V|^2 |E| )
– This algorithm works even if there are edges whose capacities are irrational numbers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.