David R. Karger
Clifford Stein
- App92.D. Applegate, 1992. personal communication.Google Scholar
- CHM90.J. Cheriyan, T. Hagerup, and S. N. Maheshwari. Can a maximum flow be computed in o(nm) time? ICALP, 1990. Google ScholarDigital Library
- DFJ54.G. B. Dantzig, D. R. Fulkerson, and S. M. Johnson. Solution of a large-scale traveling-salesman problem. Operations Research, 2:393-410, 1954.Google ScholarCross Ref
- EFS56.P. Elias, A. Feinstein, and C. E. Shannon. Note on maximum flow through a network. IRE Transactions on Information Theory IT-2, pages 117-199, 1956.Google ScholarCross Ref
- EK72.J. Edmonds and R.M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19:248-264, 1972. Google ScholarDigital Library
- FF56.L.R. Ford and D. R. Fulkerson. Maximal flow through a network. Canad. J. Math., 8:399-404, 1956.Google ScholarCross Ref
- Gab91.Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. Proceedings of the 23rd Annual A CM Symposium on Theory of Computing, May 1991. Google ScholarDigital Library
- GH61.R.E. Gomory and T. C. Hu. Multiterminal network flows. J. SIAM, 9:551- 570, 1961.Google Scholar
- GP85.Z. Galil and V. Pan. Improved processor bounds for algebraic and combinatorial problems in TiNC. Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pages 490-495, 1985. To appear in Journal of the A CM.Google ScholarDigital Library
- GSS82.L. Goldschlager, R. Shaw, and J. Staples. The maximum flow problem is log-space complete for :P. Theoretical Computer Science, 21:105-111, 1982.Google ScholarCross Ref
- GT88.A.V. Goldberg and R. E. Tarjan. A new approach to the maximum flow problem. Journal of the A CM, 35:921-940, 1988. Google ScholarDigital Library
- HO92.J. Hao and J. B. Orlin. A faster algorithm for finding the minimum cut in a graph. Proceedings of the 3rd A CM-SIAM Symposium on Discrete Algorithms, pages 165-174, January 1992. Google ScholarDigital Library
- FF62.L.R. Ford Jr. and D. R. Fulkerson. Flows in networks. Princeton University Press, 1962.Google ScholarCross Ref
- Kar93.D. Karger. Global min-cuts in TCNC, and other ramifications of a simple min-cut algorithm. Proceedings of the 4th ACM- SIAM Symposium on Discrete Algorithms, pages January 1993. Google ScholarDigital Library
- KPST91.P. Klein, S. A. Plotkin, C. Stein, and t#. Tardos. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. Technical Report 961, School of Operations Research and Industrial Engineering, Cornel1 University, 1991. A preliminary version of this paper appeared in Proceedings of the 22nd Annual A CM Symposium on Theory of Computing, pages 310-321, 1990. To appear in SIAM J. Computing. Google Scholar
- KRT92.V. King, S. Rao, and R. Tarjan. A faster deterministic maximum flow algorithm. Proceedings o} the 3rd A CM-SIAM Symposium on Discrete Algorithms, pages 157-164, January 1992. Google ScholarDigital Library
- KT86.A.V. Karzanov and E. A. Timofeev. Efficient algorithm for finding all minimal edge cuts of a non-oriented graph. Kibernetika, 22:8-12, 1986. Translation in Cybernetics 22, 1986, pages 156-162.Google Scholar
- KUW86.R. Karp, E. Upfal, and A. Wigderson. Constructing a perfect matching is in random A/'C. Combinatorica, 6:35-48, 1986. Google ScholarDigital Library
- LLKS85.E.L. Lawler, J.K. Lenstra, A.H.G. Rinooy Kan, and D.B. Shmoys, editors. The Traveling Salesman Problem. John Wiley and Sons, 1985.Google Scholar
- Mat87.D.W. Matula. Determining edge connectivity in o(nm). Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 249-251, October 1987.Google ScholarDigital Library
- MVV87.K. Mulmuley, U.V. Vazirani, and V.V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105-113, 1987. Google ScholarDigital Library
- NI92.Hiroshi Nagamochi and Toshihde Ibaraki. Computing edge connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics, 5(1):54-66, February 1992. Google ScholarDigital Library
- NV91.D. Naor and V. Vazirani. Representing and enumerating edge connectivity cuts in TiNC. Proceedings of the Second Workshop on Algorithms and Data Structures, pages 273-285, 1991. Published as Lecture Notes in Computer Science 519, Springer- Verlag.Google ScholarCross Ref
- Pod73.V.D. Podderyugin. An algorithm for finding the edge connectivity of graphs. Vopr. Kibern., 2:136, 1973.Google Scholar
- PQ82.J.C. Picard and M. Querayne. Selected applications of minimum cuts in networks. INFOR., 20:394-422, November 1982.Google ScholarCross Ref
- PR90.M. Padberg and G. Rinaldi. An efficient algorithm for the minimum capacity cut problem. Mathematical Programming, 47:19-39, 1990. Google ScholarDigital Library
- PW92.S. Phillips and J. Westbrook. Online load balancing and network flow. To appear in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993. Google ScholarDigital Library
- Ram87.V. Ramachandran. Flow value, minimum cuts and maxmium flows, 1987. Unpublished manuscript.Google Scholar
Index Terms
- An Õ(n2) algorithm for minimum cuts
Recommendations
An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computingWe present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V,E). The expected running time of our algorithm is Õ(mc) where |E| = m and c is the maximum u-vedge connectivity, where u,v ∈ V. When the ...
Global minimum cuts in surface embedded graphs
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithmsWe give a deterministic algorithm to find the minimum cut in a surface-embedded graph in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, our algorithm computes the minimum cut in gO(g)n log log n time, matching ...
Augmenting Undirected Edge Connectivity in Õ(n2) Time
We give improved randomized (Monte Carlo) algorithms for undirected edge splitting and edge connectivity augmentation problems. Our algorithms run in time (n2) on n-vertex graphs, making them an (m/n) factor faster than the best known deterministic ones ...
Comments