Approximate Max Flow on Small Depth Networks

The author considers the maximum flow problem on directed acyclic networks with m edges and depth r (length of the longest s-t path). The main result is a new deterministic algorithm for solving the relaxed problem of computing an s-t flow of value at least (1- epsilon ) of the maximum flow. For instances where r and epsilon /sup -1/ are small (i. e. , O(polylog(m))), this algorithm is in NC and uses only O(m) processors, which is a significant improvement over existing parallel algorithms. As one consequence, he obtains an NC O(m) processor algorithm to find a bipartite matching of cardinality (1- epsilon ) of the maximum (for epsilon /sup -1/ = O(polylog(m))). The parallel bounds are based on a novel approach to the blocking flow problem that produces fractional valued flow augmentations even when capacities are integral. She shows that a fractional flow on any network with integral capacities can be rounded in polylogarithmic time to an integral flow of no smaller value using O(m) processors. Hence, within the same resource bounds, an integral flow can be obtained when desired. >

Authors

• Edith Cohen

Keywords

• Parallel algorithms
• Polynomials
• Integral equations
• Phase change random access memory
• Network Depth
• Flow Algorithm
• Maximum Flow
• Flow Values
• Network Flow
• Flow Problem
• Amount Of Flow
• Current Capacity
• Fractional Flow
• Parallel Algorithm
• Network Units
• Breadth-first Search
• Maximum Matching
• Modification Of Algorithm
• Planar Graphs
• Graph Matching
• Bipartite Matching
• Approximate Matching
• Minimum Cost Flow
• Back Edge
• Power-of-two
• Current Flow
• Conservation Constraints
• Running Time
• Edge Labels
• End Edge
• Matrix Multiplication
• First Search