Approximating s--t minimum cuts in ~O(n^2) time

by András A. Benczúr and David R. Karger

Proc. 28th Annual Symp. on Theory of Comp. (1996), pages 47-55, Philadelphia, Pennsylvania, 22-24 May 1996.

ps.gz ps pdf

Document in Citeseer database
For some reason this paper has an incredible number of additional entries in the database: #1, #2, #3, #4, #5.

Reference in context as in the Hypertext Bibliography Project (apparently not maintained since 1998)

Related articles

The paper appears in a refereed version in my Ph.D. Thesis. Also read the excellent surveys of David Karger (and Cliff Stein), Random sampling in cut, flow, and network design problems Math. Oper. Res. 24: (2) 383-413 May 1999, and A new approach to the minimum cut problem. Journal of the ACM, 43(4):601-640, July 1996.

Citations

  1. R. Kannan, S. Vempala, and A. Vetta
    On Clusterings. Good, Bad and Spectral
    41st Annual Symposium on Foundations of Computer Science 12-14 November, 2000 Redondo Beach, California
  2. Asano T, Asano Y
    Recent developments in maximum flow algorithms
    J OPER RES SOC JPN 43: (1) 2-31 MAR 2000
  3. Andrew Goldberg,
    Recent developments in Maximum Flow Algorithms,
    TR \#98-045 NEC Research Institute
  4. Goldberg AV
    Recent developments in maximum flow algorithms (invited lecture)
    LECT NOTES COMPUT SC 1432: 1-10 1998
  5. Andrew Goldberg, Satish Rao
    Length Functions for Flow Computations,
    TR \#97-055 NEC Research Institute
  6. Leighton T, Rao S
    Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
    J ACM 46: (6) 787-832 NOV 1999
  7. Feige, Krauthgamer, Nissim
    Approximating the minimum bisection size, STOC 2000
  8. Feige, Krauthgamer
    A polylogarithmic approximation of the minimum bisection size, FOCS 2000
  9. Guy Even, Joseph (Seffi) Naor, and Leonid Zosin
    An 8-approximation algorithm for the subset feedback vertex set problem.
    In 37th Annual Symposium on Foundations of Computer Science, pages 310-319, Burlington, Vermont, 14-16 October 1996. IEEE.
  10. Andrew V. Goldberg and Satish Rao.
    Beyond the flow decomposition barrier.
    In 38th Annual Symposium on Foundations of Computer Science, pages 2-11, Miami Beach, Florida, 20-22 October 1997. IEEE.
  11. Ravi Kannan, S Vempala, A Vetta
    On Clusterings --- Good, Bad and Spectral