Abstract
The problem of finding the minimum cut of an undirected unweighted graph is studied on the external memory model. First, a lower bound of Ω((E/V) Sort(V)) on the number of I/Os is shown for the problem, where V is the number of vertices and E is the number of edges. Then the following are presented, for M = Ω(B 2), (1) a minimum cut algorithm that uses \(O(c \log E ({\rm MSF}{(V,E)} + \frac{V}{B} {\rm Sort}({V})))\) I/Os; here MSF(V,E) is the number of I/Os needed to compute a minimum spanning tree of the graph, and c is the value of the minimum cut. The algorithm performs better on dense graphs than the algorithm of [7], which requires O(E + c 2 V log(V/c)) I/Os, when executed on the external memory model. For a δ-fat graph (for δ > 0, the maximum tree packing of the graph is at least (1 + δ)c/2), our algorithm computes a minimum cut in O(c logE (MSF(V,E) + Sort(E))) I/Os. (2) a randomized algorithm that computes minimum cut with high probability in \(O(c \log E \cdot{\rm MSF}{(V,E)} + {\rm Sort}{(E)} \log^2 V + \frac{V}{B} {\rm Sort}{(V)} \log V)\) I/Os. (3) a (2 + ε)-minimum cut algorithm that requires O((E/V) MSF(V,E)) I/Os and performs better on sparse graphs than our exact minimum cut algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, A., Vitter, J.S.: The input/output complexity of sorting and related problems. Commun. ACM 31(9), 1116–1127 (1988)
Aggarwal, G., Datar, M., Rajagopalan, S., Ruhl, M.: On the streaming model augmented with a sorting primitive. In: Proc. IEEE Symposium on Foundations of Computer Science, pp. 540–549 (2004)
Alka: Efficient algorithms and data structures for massive data sets, Ph.D. thesis, Indian Institute of Technology Guwahati, India (2009), http://arxiv.org/abs/1005.3473
Brinkmeier, M.: A simple and fast min-cut algorithm. Theor. Comp. Sys. 41(2), 369–380 (2007)
Chiang, Y.J., Goodrich, M.T., Grove, E.F., Tamassia, R., Vengroff, D.E., Vitter, J.S.: External memory graph algorithms. In: Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 139–149 (1995)
Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399–404 (1956)
Gabow, H.N.: A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci. 50(2), 259–273 (1995)
Goldschlager, L.M., Shaw, R.A., Staples, J.: The maximum flow problem is LOGSPACE complete for P. Theoret. Comput. Sci. 21(1), 105–111 (1982)
Hao, J., Orlin, J.: A faster algorithm for finding the minimum cut in a graph. J. Algorithms 17(3), 424–446 (1994)
Karger, D.R.: Minimum cuts in near linear time. J. ACM 47(1), 46–76 (2000)
Karger, D.R., Motwani, R.: An NC algorithm for minimum cuts. SIAM J. Comput. 26(1), 255–272 (1997)
Matula, D.W.: A linear time 2 + ε approximation algorithm for edge connectivity. In: Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 500–504 (1993)
Mungala, K., Ranade, A.: I/O-complexity of graph algorithms. In: Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 687–694 (1999)
Nagamochi, H., Ibaraki, T.: A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica 7(5-6), 583–596 (1992)
Nash-Williams, C.S.J.A.: Edge-disjoint spanning tree of finite graphs. J. London Math. Soc. 36, 445–450 (1961)
Plotkin, S.A., Shmoys, D.B., Tardos, É.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2), 257–301 (1995)
Stoer, M., Wagner, F.: A simple min-cut algorithm. J. ACM 44(4), 585–591 (1997)
Thorup, M., Karger, D.R.: Dynamic graph algorithms with applications. In: Halldórsson, M.M. (ed.) SWAT 2000. LNCS, vol. 1851, pp. 1–9. Springer, Heidelberg (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Bhushan, A., Sajith, G. (2014). I/O Efficient Algorithms for the Minimum Cut Problem on Unweighted Undirected Graphs. In: Pal, S.P., Sadakane, K. (eds) Algorithms and Computation. WALCOM 2014. Lecture Notes in Computer Science, vol 8344. Springer, Cham. https://doi.org/10.1007/978-3-319-04657-0_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-04657-0_19
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04656-3
Online ISBN: 978-3-319-04657-0
eBook Packages: Computer ScienceComputer Science (R0)