snippetMinor
how to check whether a flow network contains unique maximum flow?
Viewed 0 times
uniqueflowmaximumcontainshowcheckwhethernetwork
Problem
I have been stuck on this problem for few hours, my assignment asks to design an efficient algorithm(polynomial running time) that check whether a given flow network graph contains a unique maximum flow or not. I have been search everything I could, and some people said run an algorithm that able to find a max flow first, then modified the edges capacity, and run the algorithm one more time to see if we get the same flow value. But this seems never works for me especially when we are given arbitrary flow network, like non-integer flow graph. How should I start a good approach? (Literally stuck for few hours)
Solution
Find a maximum flow. Then create m new flow networks: one for each edge in the maximum flow. In each new configuration, reduce the capacity of one of the edges to an amount just below its flow. Find the maximum flow on each of the new flow networks. If any of the new configurations generate the same maximum flow value as the original graph, then that new flow is also a maximum flow in the original graph. Hence, the original maximum flow is not unique.
Context
StackExchange Computer Science Q#117242, answer score: 4
Revisions (0)
No revisions yet.