Max flow problem and push relabel algorithem

1. Maximum Flow Push relabel algorithm By Waqas Shehzad Fast NU P akistan

2. Push-Relabel Push-relabel algorithm is described by Dr. Andrew Goldberg and Robert E.Tarjan. Leads to better running times, both in theory and practice. All previous Network Flow related algorithms are related to augmentation . A draw back of aug-based schemes: each augmentation takes O(n ) time. Multiple augmentations may partially share paths, but it’s not exploited by algorithms . Not very hard to code. Push relabel is consider as the Fastest maximum-flow algorithm.

3. Preflow -Basics Preflow algorithm allow temporary imbalance (excess) at nodes , and work towards feasibility . push-relabel algorithms work on one vertex at a time, looking only at the vertex’s neighbors. “pushing” preflow and “relabeling” a vertex relabeling Formally, a preflow is a function ƒ: V×V → R that satisfies capacity constraints and In preflow algorithm a graph is consider to have two special nodes Source and Sink  

4. Cont.. P P reflow : A labeling h : V  Z+ is compatible with a preflow if

5. C ode for Preflow -Push

6. Run time Generic Preflow -Push algorithm runs in worst-case time 0 ). The total number of saturating push operations is at most m . The total number of nonsaturating push operations is at most 2nm . The total number of relabeling operations is less than 2 . This running time is farther improved with Highest-label rule, Excess scaling,  

7. References Lecturer: Julian Mestre Optimization II Lecture 3 Andrew V. Goldberg and Robert E. Tarjan , A new approach to the maximum-flow problem. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest . Introduction to Algorithms. Algorithm Tutorial: MaximumFlow Algorithm Tutorial: Introduction to graphs and their data structures http://iss.ices.utexas.edu/?p=projects/galois/benchmarks/preflow_push