c Balaji Raghavachari 222 Algorithm Design and Analysis Running time of max ow algorithms R T of Ford Fulkerson s algorithm is nite but unbounded when all capacities are rational numbers If a shortest augmenting path in terms of number of hops is found using BFS then running time becomes polynomial Edmonds Karp s algorithm based on this idea O E 2 V Dinitz gave an algorithm that nds all shortest augmenting paths at the same time O E V 2 Malhotra Kumar Maheswari showed how to nd a blocking ow in O V 2 and max ow in O V 3 time Other methods have been introduced recently Scaling algorithm Pre ow Push algorithms c Balaji Raghavachari 223 Algorithm Design and Analysis Bipartite matching problem A subgraph M is called a matching if the degree of every node in M is at most 1 Matching shown above thick edges is a maximal matching similar to blocking ow a matching in which no additional edges can be added to the set without 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 ow s t Input graph The capacity of each edge is made to be 1 It can be shown that a matching of cardinality M exists if and only if there is a ow of M units Therefore a maximum cardinality matching can be computed by nding a maximum ow in the ow problem constructed c Balaji Raghavachari 225 Algorithm Design and Analysis Closing remarks Ford Fulkerson algorithm shows that if capacities are integers then there exists a maximum ow in which all ow values are also integers Multiple source multiple sink problem can be reduced to the single source single sink max ow problem Add a new super source node and connect it by edges of capacity to the given sources similarly a super sink Sources with bounded generating capacity split source into two nodes connected by an edge of capacity equal to the generating capacity of the source Other extensions multi commodity ow min cost ow Graph network connectivity disjoint paths from u to v can be computed using max ow algorithms c Balaji Raghavachari 226 Algorithm Design and Analysis Multi commodity ow Di erent commodities ow through the same network For each vertex ow conservation must be satis ed for each commodity Capacity of edge must be at least the sum of the ows of all commodities through it Multi commodity ow problem is solvable in polynomial time using algorithms for linear programming Unlike sigle commodity ow integer solution cannot be guaranteed Finding an integer optimal solution to Multi commodity ow problem is NP hard
View Full Document
Unlocking...