{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T04:33:46Z","timestamp":1725770026824},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319046563"},{"type":"electronic","value":"9783319046570"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-04657-0_19","type":"book-chapter","created":{"date-parts":[[2014,1,17]],"date-time":"2014-01-17T05:19:32Z","timestamp":1389935972000},"page":"188-199","source":"Crossref","is-referenced-by-count":0,"title":["I\/O Efficient Algorithms for the Minimum Cut Problem on Unweighted Undirected Graphs"],"prefix":"10.1007","author":[{"given":"Alka","family":"Bhushan","sequence":"first","affiliation":[]},{"given":"G.","family":"Sajith","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"9","key":"19_CR1","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM\u00a031(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"unstructured":"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\u2013549 (2004)","key":"19_CR2"},{"unstructured":"Alka: Efficient algorithms and data structures for massive data sets, Ph.D. thesis, Indian Institute of Technology Guwahati, India (2009), \n                    \n                      http:\/\/arxiv.org\/abs\/1005.3473","key":"19_CR3"},{"issue":"2","key":"19_CR4","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s00224-007-2010-2","volume":"41","author":"M. Brinkmeier","year":"2007","unstructured":"Brinkmeier, M.: A simple and fast min-cut algorithm. Theor. Comp. Sys.\u00a041(2), 369\u2013380 (2007)","journal-title":"Theor. Comp. Sys."},{"unstructured":"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\u2013149 (1995)","key":"19_CR5"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L.R. Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math.\u00a08, 399\u2013404 (1956)","journal-title":"Can. J. Math."},{"issue":"2","key":"19_CR7","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1006\/jcss.1995.1022","volume":"50","author":"H.N. Gabow","year":"1995","unstructured":"Gabow, H.N.: A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci.\u00a050(2), 259\u2013273 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"19_CR8","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0304-3975(82)90092-5","volume":"21","author":"L.M. Goldschlager","year":"1982","unstructured":"Goldschlager, L.M., Shaw, R.A., Staples, J.: The maximum flow problem is LOGSPACE complete for P. Theoret. Comput. Sci.\u00a021(1), 105\u2013111 (1982)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"19_CR9","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1006\/jagm.1994.1043","volume":"17","author":"J. Hao","year":"1994","unstructured":"Hao, J., Orlin, J.: A faster algorithm for finding the minimum cut in a graph. J. Algorithms\u00a017(3), 424\u2013446 (1994)","journal-title":"J. Algorithms"},{"issue":"1","key":"19_CR10","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/331605.331608","volume":"47","author":"D.R. Karger","year":"2000","unstructured":"Karger, D.R.: Minimum cuts in near linear time. J. ACM\u00a047(1), 46\u201376 (2000)","journal-title":"J. ACM"},{"issue":"1","key":"19_CR11","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/S0097539794273083","volume":"26","author":"D.R. Karger","year":"1997","unstructured":"Karger, D.R., Motwani, R.: An NC algorithm for minimum cuts. SIAM J. Comput.\u00a026(1), 255\u2013272 (1997)","journal-title":"SIAM J. Comput."},{"unstructured":"Matula, D.W.: A linear time 2\u2009+\u2009\u03b5 approximation algorithm for edge connectivity. In: Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 500\u2013504 (1993)","key":"19_CR12"},{"unstructured":"Mungala, K., Ranade, A.: I\/O-complexity of graph algorithms. In: Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 687\u2013694 (1999)","key":"19_CR13"},{"issue":"5-6","key":"19_CR14","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica\u00a07(5-6), 583\u2013596 (1992)","journal-title":"Algorithmica"},{"key":"19_CR15","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"36","author":"C.S..J.A. Nash-Williams","year":"1961","unstructured":"Nash-Williams, C.S.J.A.: Edge-disjoint spanning tree of finite graphs. J. London Math. Soc.\u00a036, 445\u2013450 (1961)","journal-title":"J. London Math. Soc."},{"issue":"2","key":"19_CR16","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"S.A. Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res.\u00a020(2), 257\u2013301 (1995)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"19_CR17","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1145\/263867.263872","volume":"44","author":"M. Stoer","year":"1997","unstructured":"Stoer, M., Wagner, F.: A simple min-cut algorithm. J. ACM\u00a044(4), 585\u2013591 (1997)","journal-title":"J. ACM"},{"key":"19_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44985-X_1","volume-title":"Algorithm Theory - SWAT 2000","author":"M. Thorup","year":"2000","unstructured":"Thorup, M., Karger, D.R.: Dynamic graph algorithms with applications. In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 1\u20139. Springer, Heidelberg (2000)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-04657-0_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T23:33:22Z","timestamp":1558827202000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-04657-0_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319046563","9783319046570"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-04657-0_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}