András A. Benczúr
David R. Karger
- AMO93.Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993. Google Scholar
Digital Library
- Che52.H. Chemoff. A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics, 23:493-509, 1952.Google ScholarCross Ref
- CLR90.Thomas H. Cormen, Charles E. Leiserson, and, Ronald L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1990. Google ScholarDigital Library
- DRT92.Brandon Dixon, Monika Rauch, and Robert E. Tarjan. Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM Journal on Computing, 21(6):1184--1192, 1992. Google ScholarDigital Library
- FF56.Lester R. Ford, Jr. and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399--404, 1956.Google ScholarCross Ref
- Gab95.Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. Journal of Computer and System Sciences, 50(2):259-273, April 1995. A preliminary version appeared in STOC 1991. Google ScholarDigital Library
- GT88.Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum flow problem. Journal of the ACM, 35:921-940, 1988. Google ScholarDigital Library
- Kar94a.David R. Karger. Random sampling in cut, flow, and network design problems. In Proceedings of the 26th A CM Symposium on Theory of Computing, pages 648--657. ACM, ACM Press, May 1994. Submitted to Mathematics of Operations Research. Google ScholarDigital Library
- Kar94b.David R. Karger. Using randomized sparsification to approximate minimum cuts. In Proceedings of the 5th Annual A CM-SIAM Symposium on Discrete Algorithms, pages 424--432. ACM-SIAM, January 1994. Arlington, VA, Google ScholarDigital Library
- Kar96.David R. Karger. Minimum cuts in near-linear time. In Proceedings of the 28th A CM Symposium on Theory of Computing. ACM, ACM Press, May 1996. Philadelphia, PA. Google ScholarDigital Library
- KST90.Philip N. Klein, Clifford Stein, and Eva Tardos. Leighton-Rao might be practical: Faster approximation algorithms for concurrent flow with uniform capacities. In Proceedings of the 22~a A CM Symposium on Theory of Computing, pages 310- 321. ACM, ACM Press, May 1990. Google ScholarDigital Library
- NI92a.Hiroshi Nagamochi and Toshihide Ibaraki. Computing edge connectivity in multigraphs and capacitated graphs. SIAM Journal of Discrete Mathematics, 5(1):54--66, February 1992. Google ScholarDigital Library
- NI92b.Hiroshi Nagamochi and Toshihide Ibaraki. Linear time algorithms for finding k-edge connected and k-node connected spanning subgraphs. Algorithmica, 7:583-596, 1992.Google ScholarCross Ref
Index Terms
- Approximating s-t minimum cuts in Õ(n2) time
Recommendations
Unbalanced graph cuts with minimum capacity
We systematically investigate minimum capacity unbalanced cut problems arising in social networks. Let k be an input parameter. A cut (A, B) is unbalanced if the size of its smaller side is at most k (called k-size) or exactly k (called Ek-size). An s-t ...
A rounding algorithm for approximating minimum Manhattan networks
For a set T of n points (terminals) in the plane, a Manhattan network on T is a network N(T)=(V,E) with the property that its edges are horizontal or vertical segments connecting points in V@?T and for every pair of terminals, the network N(T) contains ...
Approximating Tverberg Points in Linear Time for Any Fixed Dimension
Let $$P \subseteq \mathbb{R }^d$$P⊆Rd be a $$d$$d-dimensional $$n$$n-point set. A Tverberg partition is a partition of $$P$$P into $$r$$r sets $$P_1, \dots , P_r$$P1,ź,Pr such that the convex hulls $$\hbox {conv}(P_1), \dots , \hbox {conv}(P_r)$$conv(P1)...
Comments