Explore BrainMass
Share

Network Flows

This is a problem about Network Flows.
A. The Edmonds Karp max-flow algorithm uses Breadth First Search to find the augmenting path. What is the running time of the Edmonds-Karp algorithm to find the maximum flow?
B. Here is a flow network. Trace the execution of the Edmonds-Karp algorithm to find the maximum flow. Draw a separate picture for each augmenting step - clearly showing the residual graph and the flow network. What is the value of the maximum flow?

C. What is the value of the maximum flow? (Your answer should be a number.)
D. Give a minimum cut for this flow network. (Your answer should be two sets of vertices, S and T.)

© BrainMass Inc. brainmass.com June 20, 2018, 5:37 am ad1c9bdddf

Attachments

Solution Preview

This is a problem about Network Flows.

A. The Edmonds Karp max-flow algorithm uses Breadth First Search to find the augmenting path. What is the running time of the Edmonds-Karp algorithm to find the maximum flow?
O(VE2)
B. Here ...

Solution Summary

Network Flows are highlighted.

$2.19