Random sampling in residual graphs

ABSTRACT

Consider an n-vertex, m-edge, undirected graph with maximum flow value v. We give a new Õ(m+nv)-time maximum flow algorithm based on finding augmenting paths in random samples of the edges of residual graphs. After assigning certain special sampling probabilities to edges in Õ(m) time, our algorithm is very simple: repeatedly find an augmenting path in a random sample of edges from the residual graph.

REFERENCES

• 1: András A. Benczúr , David R. Karger, Approximating s-t minimum cuts in Õ(n²) time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.47-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237827]
• 2: S. Even and R. E. Tarjan. Network Flow and Testing Graph Connectivity. SIAM Journal on Computing, 4:507--518, 1975.
• 3: L. R. Ford, Jr. and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of (MATH)ematics, 8:399--404, 1956.
• 4: A. V. Goldberg , S. Rao, Beyond the flow decomposition barrier, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.2, October 19-22, 1997
• 5: A. V. Goldberg , S. Rao, Flows in undirected unit capacity networks, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.32, October 19-22, 1997
• 6: IEEE. Proceedings of the 30th Annual Symposium on the Foundations of Computer Science. IEEE Computer Society Press, Oct. 1997.
• 7: David R. Karger, Using random sampling to find maximum flows in uncapacitated undirected graphs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.240-249, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258596]
• 8: David R. Karger, Better random sampling algorithms for flows in undirected graphs, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.490-499, January 25-27, 1998, San Francisco, California, United States
• 9: A. A. Tsay , W. S. Lovejoy , David R. Karger, Random Sampling in Cut, Flow, and Network Design Problems, Mathematics of Operations Research, v.24 n.2, p.383-413, February 1999 [doi>10.1287/moor.24.2.383]
• 10: David R. Karger , Matthew S. Levine, Finding maximum flows in undirected graphs seems easier than bipartite matching, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.69-78, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276714]
• 11: David R. Karger , Clifford Stein, A new approach to the minimum cut problem, Journal of the ACM (JACM), v.43 n.4, p.601-640, July 1996 [doi>10.1145/234533.234534]
• 12: H. Nagamochi and T. Ibaraki. Linear time algorithms for finding k-edge connected and k-node connected spanning subgraphs. Algorithmica, 7:583--596, 1992.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

General Terms:
Measurement, Performance, Theory