Thought Exercise: Rational Capacities
Learn how to use the Ford-Fulkerson algorithm when dealing with rational edge capacities.
We'll cover the following
Changing rational capacities to integers
We know that the Ford-Fulkerson algorithm terminates when the graph has integer capacities. Suppose we are faced with a flow network that has rational numbers as edge capacities. To guarantee that the algorithm terminates, we would like to use the following strategy:
- Change the rational capacities to integer values in some systematic way.
- Run the Ford-Fulkerson algorithm to find max flow with respect to the changed capacities.
- Recover the flow in the flow network with respect to the original rational capacities.
Get hands-on with 1200+ tech skills courses.