{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:16:51Z","timestamp":1781259411313,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662451731","type":"print"},{"value":"9783662451748","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-45174-8_30","type":"book-chapter","created":{"date-parts":[[2014,9,29]],"date-time":"2014-09-29T11:28:20Z","timestamp":1411990100000},"page":"439-453","source":"Crossref","is-referenced-by-count":30,"title":["Almost-Tight Distributed Minimum Cut Algorithms"],"prefix":"10.1007","author":[{"given":"Danupon","family":"Nanongkai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hsin-Hao","family":"Su","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"5","key":"30_CR1","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"A. Das Sarma","year":"2012","unstructured":"Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput.\u00a041(5), 1235\u20131265 (2012)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"30_CR2","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":"30_CR3","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/S0097539794261118","volume":"27","author":"J.A. Garay","year":"1998","unstructured":"Garay, J.A., Kutten, S., Peleg, D.: A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput.\u00a027(1), 302\u2013316 (1998)","journal-title":"SIAM J. Comput."},{"key":"30_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-41527-2_1","volume-title":"Distributed Computing","author":"M. Ghaffari","year":"2013","unstructured":"Ghaffari, M., Kuhn, F.: Distributed minimum cut approximation. In: Afek, Y. (ed.) DISC 2013. LNCS, vol.\u00a08205, pp. 1\u201315. Springer, Heidelberg (2013)"},{"key":"30_CR5","unstructured":"Karger, D.R.: Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In: SODA, pp. 21\u201330 (1993)"},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"Karger, D.R.: Random sampling in cut, flow, and network design problems. In: STOC, pp. 648\u2013657 (1994)","DOI":"10.1145\/195058.195422"},{"key":"30_CR7","unstructured":"Karger, D.R.: Using randomized sparsification to approximate minimum cuts. In: SODA, pp. 424\u2013432 (1994)"},{"issue":"1","key":"30_CR8","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"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"Karger, D.R., Stein, C.: An \n                    \n                      \n                    \n                    $\\tilde{O}(n^2)$\n                   algorithm for minimum cuts. In: STOC, pp. 757\u2013765 (1993)","DOI":"10.1145\/167088.167281"},{"issue":"6","key":"30_CR10","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s00446-007-0047-8","volume":"20","author":"M. Khan","year":"2008","unstructured":"Khan, M., Pandurangan, G.: A fast distributed approximation algorithm for minimum spanning trees. Distributed Computing\u00a020(6), 391\u2013402 (2008)","journal-title":"Distributed Computing"},{"issue":"1","key":"30_CR11","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1006\/jagm.1998.0929","volume":"28","author":"S. Kutten","year":"1998","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. J. Algorithms\u00a028(1), 40\u201366 (1998)","journal-title":"J. Algorithms"},{"issue":"2","key":"30_CR12","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1137\/080714403","volume":"39","author":"Z. Lotker","year":"2009","unstructured":"Lotker, Z., Patt-Shamir, B., Ros\u00e9n, A.: Distributed approximate matching. SIAM J. Comput.\u00a039(2), 445\u2013460 (2009)","journal-title":"SIAM J. Comput."},{"key":"30_CR13","unstructured":"Matula, D.W.: A linear time 2\u2009+\u2009\u03b5 approximation algorithm for edge connectivity. In: SODA, pp. 500\u2013504 (1993)"},{"issue":"1","key":"30_CR14","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0405004","volume":"5","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Discret. Math.\u00a05(1), 54\u201366 (1992)","journal-title":"SIAM J. Discret. Math."},{"key":"30_CR15","doi-asserted-by":"crossref","unstructured":"Nanongkai, D.: Brief announcement: Almost-tight approximation distributed algorithm for minimum cut. In: PODC, pp. 382\u2013384 (2014)","DOI":"10.1145\/2611462.2611511"},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: STOC, pp. 565\u2013573 (2014)","DOI":"10.1145\/2591796.2591850"},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Nash-Williams, C.S.J.A.: Edge-disjoint spanning trees of finite graphs. J. London Math. Soc.\u00a0s1-36(1), 445\u2013450 (1961)","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"30_CR18","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications (2000)","DOI":"10.1137\/1.9780898719772"},{"issue":"4","key":"30_CR19","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/2000807.2000814","volume":"7","author":"D. Pritchard","year":"2011","unstructured":"Pritchard, D., Thurimella, R.: Fast computation of small cuts via cycle space sampling. ACM Transactions on Algorithms\u00a07(4), 46 (2011)","journal-title":"ACM Transactions on Algorithms"},{"issue":"4","key":"30_CR20","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":"30_CR21","doi-asserted-by":"crossref","unstructured":"Su, H.H.: Brief annoucement: A distributed minimum cut approximation scheme. In: SPAA, pp. 217\u2013219 (2014)","DOI":"10.1145\/2612669.2612706"},{"issue":"1","key":"30_CR22","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00493-007-0045-2","volume":"27","author":"M. Thorup","year":"2007","unstructured":"Thorup, M.: Fully-dynamic min-cut. Combinatorica\u00a027(1), 91\u2013127 (2007)","journal-title":"Combinatorica"},{"issue":"1","key":"30_CR23","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1006\/jagm.1996.0832","volume":"23","author":"R. Thurimella","year":"1997","unstructured":"Thurimella, R.: Sub-linear distributed algorithms for sparse certificates and biconnected components. J. Algorithms\u00a023(1), 160\u2013179 (1997)","journal-title":"J. Algorithms"},{"issue":"1","key":"30_CR24","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1112\/jlms\/s1-36.1.221","volume":"s1-36","author":"W.T. Tutte","year":"1961","unstructured":"Tutte, W.T.: On the problem of decomposing a graph into n connected factors. J. London Math. Soc.\u00a0s1-36(1), 221\u2013230 (1961)","journal-title":"J. London Math. Soc."}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-45174-8_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T20:38:38Z","timestamp":1558989518000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-45174-8_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662451731","9783662451748"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-45174-8_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}