c� Balaji Raghavachari 222 Algorithm Design and Analysis✬✫✩✪Running time of max-flow algorithms• R.T. of Ford-Fulkerson’s algorithm is finite butunbounded (when all capacities are rational numbers).• If a shortest augmenting path (in ter ms of number ofhops) is found (using BFS), then running t ime becomespolynomial. Edmonds-Karp’s algorithm based on thisidea: O(|E|2|V |).• Dinitz gave an algorithm that finds all shortestaugmenting paths at the same time: O(|E||V |2).• Malhotra-Kumar-Maheswari showed how to find ablocking flow in O(|V |2), and max flow in O(|V |3) time.• Other methods have been introduced recently: Scalingalgorithm, Pre-flow/Push algorithms.c� Balaji Raghavachari 223 Algorithm Design and Analysis✬✫✩✪Bipartite m atching problem• A subgraph M is called a matching if the degree ofevery node in M is at most 1.• Matching shown above (thick edges) is a maximalmatching (similar to block ing flow): a matching inwhich no additional edges can be added to the setwithout violating degree constraint of a matching.• M is a perfect matching if all nodes of G is matched.c� Balaji Raghavachari 224 Algorithm Design and Analysis✬✫✩✪Reducing bipartite matching to max-flows tInput graph• The capacity of each edge is ma de to be 1.• It can be shown that a matching of cardinality |M |exists if and only if there is a flow of |M | units.• Therefore a maximum cardinality matching can becomputed by finding a maximum flow in the flowproblem constructed.c� Balaji Raghavachari 225 Algorithm Design and Analysis✬✫✩✪Closing remarks• Ford-Fulkerson algorithm shows that if capacities areintegers, then there exists a ma ximum flow in which allflow values are also integers.• Multiple-source, multiple-sink problem can be reducedto the single-source, single-sink max-flow problem. Adda new “super source” node a nd connect it by edges ofcapacity ∞ to the given sources (sim ilarly a super sink).• Sources with bounded generating capacity: split sourceinto two nodes, connected by an edge of capacity equalto the generating capacity of the source.• Other extensions: multi-commodity flow, min-cost flow.• Graph/network connectivity (disjoint paths from u to v)can be computed using max- flow algorithms.c� Balaji Raghavachari 226 Algorithm Design and Analysis✬✫✩✪Multi-commodity flow• Different commodities flow through the same network.For each vertex, flow conservation must be satisfied foreach commodity. Capacity of edge must be at least thesum of the flows of all commodities through it.• Multi-commodity flow problem is solva ble in polynomialtime using algorithms for linear programming.• Unlike sigle-commodity flow, integer solution cannot beguaranteed. Finding an integer optimal solution toMulti-commodity flow problem is NP-
View Full Document
Unlocking...