A Randomized Maximum-Flow Algorithm

The authors present a randomized maximum-flow algorithm, called the PLED (prudent linking excess diminishing) algorithm, whose expected running time is O(nm+n/sup 2/(log n)/sup 3/); this is O(nm) for all except relatively sparse networks. The algorithm is always correct, and in the worst case, which occurs with negligible probability, it take O(nm log n) time. The approach taken is to maintain a parameter Delta, which is a measure of the maximum flow excess of a vertex and of the maximum amount of flow sent by a single operation. Initially, Delta is less than or equal to the maximum edge capacity, and Delta =0 at termination. The execution of the PLED algorithm is partitioned into phases so that Delta stays fixed during each phase and decreases between consecutive phases. In order to achieve a bound on the number of phases that is independent of the maximum edge capacity, the algorithm decreases Delta by as large a factor (>or=2) as possible, rather than by a constant factor. The algorithm uses the dynamic trees data structure. >

Authors

• Joseph Cheriyan
• Torben Hagerup

Keywords

• Tree data structures
• Partitioning algorithms
• Labeling
• Polynomials
• Computer networks
• Joining processes
• Fluid flow measurement
• Bipartite graph
• Heuristic algorithms
• Contracts
• Maximum Flow
• Running Time
• Number Of Steps
• Structural Dynamics
• Generation Algorithm
• Selection Step
• Root Of The Tree
• Network Flow
• Start Of Phase
• Amount Of Flow
• Add Value
• Algorithm Execution
• Consecutive Phases
• Undirected Edges
• Dynamic Tree
• Incident Edges
• Number Of Bundles
• Tree Edges
• Individual Edges
• Back Edge