András A. Benczúr
- 1.Cai, G-P. and Y-G. Sun, The minimum augmentation of any graph to a k-edge-connected graph, Networks, 19 (1989), pp. 151-172.Google Scholar
Cross Ref
- 2.Dinits, E.A., A.V. Karzanov and M.L. Lomonosov, On the structure of a family of minimal weighted cuts in a graph, Studies in Discrete Optimization (in Russian), A.A. Fridman (Ed), Nauka, Moscow (1976), pp. 290-306.Google Scholar
- 3.Frank, A., Augmenting graphs to meet edge connectivity requirements, Proc. 31st Annual Symp. on Found. of Comp. Sci. (1990), and SIAM J. Discr. Math. 5 (1992) No. 1, pp. 25-53. Google ScholarDigital Library
- 4.Gabow, H.N., A matroid approach to finding edge connectivity and packing arborescences, Proc. 23rd Annual ACM Syrup. on Theory of Comp. (1991), pp. 112-122. Google ScholarDigital Library
- 5.Gabow, H.N., Applications of a poset representation to edge connectivity and graph rigidity, Proc. 32nd Annual Symp. on Found. of Comp. Sci. (1991), pp. 812-821. Google ScholarDigital Library
- 6.Gabow, H.N., Applications of a poset representation to edge connectivity and graph rigidity, Dept. ofComp. Sci., University of Colorado, Techn. Rept. CU-CS-545-91 (1991).Google Scholar
- 7.Gabow, H.N., Efficient Splitting Off Algorithms for Graphs, these proceedings. Google ScholarDigital Library
- 8.Goldberg, A.V. and R.E. Tarjan, A new approach to the maximum flow problem, Journal of the ACM, 35 (1988), pp. 921-940. Google ScholarDigital Library
- 9.Gomory, R.E. and T.C. Hu, Multi-terminal network flows. SIAM J. Appl. Math. 9 (1961), pp. 551-560.Google ScholarCross Ref
- 10.Hao, J. and J. B. Orlin, A faster algorithm for finding the minimum cut in a graph, Proc. of 3rd ACM-SIAM Symposium on Discrete Algorithms (i 992), pp. 165-174. Google ScholarDigital Library
- 11.Karger, D.R., Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm, Proc. of 4th ACM-SIAM Symposium on Discrete Algorithms, (1993), pp. 21-30. Google ScholarDigital Library
- 12.Karger, D.R. and C. Stein, An 0(n2) Algorithm for Minimum Cuts, Proc. 25th Annuai ACM Syrup. on Theory of Comp. (1993), pp. 757-765. Google ScholarDigital Library
- 13.Karzanov, A.V. and E.A. Timofeev, Efficient Algorithms for Finding all Minimal Edge Cuts of a Nonoriented Graph, Cybernetics 156-162, translated from Kibernetika 2 (1986), pp. 8-12.Google Scholar
- 14.Mulmuley, K., U.V. Vazirani and V.V. Vazirani, Matching is as easy as matrix inversion, Combinatonca 7(1 ) (1987), pp. 105-113 Google ScholarDigital Library
- 15.Naor, D., D. Gusfield, Ch. Martel, A fast algorithm for optimally increasing the edge connectivity, Proc. 31st Annual IEEE Symposium on Foundations of Comp. Sci. (1990), pp. 698-707.Google ScholarDigital Library
- 16.Naor, D. and V.V. Vazirani, Representing and enumerating edge connectivity cuts in RNC, Proc. Second Workshop on Algorithms and Data Structures (1991 ), Lecture Notes in Computer Science 519, Springer-Verlag, pp. 273-285.Google Scholar
- 17.Watanabe, T. and A. Nakamura, Edge connectivity augmentation problems, Comp. System Sci. 35 (1987), pp. 96-144. Google ScholarDigital Library
Index Terms
- Augmenting undirected connectivity in RNC and in randomized Õ(n3) time
Recommendations
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 ...
Dynamic bridge-finding in õ(log2 n) amortized time
SODA '18: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete AlgorithmsWe present a deterministic fully-dynamic data structure for maintaining information about the bridges in a graph. We support updates in Õ((log n)2) amortized time, and can find a bridge in the component of any given vertex, or a bridge separating any ...
An Optimal Randomised Logarithmic Time Connectivity Algorithm for the EREW PRAM
Improving a long chain of works, we obtain a randomised EREW PRAM algorithm for finding the connected components of a graphG=(V, E) withnvertices andmedges inO(logn) time using an optimal number ofO((m+n)/logn) processors. The result returned by the ...
Comments