{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:33:58Z","timestamp":1782970438247,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642415265","type":"print"},{"value":"9783642415272","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-41527-2_1","type":"book-chapter","created":{"date-parts":[[2013,10,3]],"date-time":"2013-10-03T14:55:48Z","timestamp":1380812148000},"page":"1-15","source":"Crossref","is-referenced-by-count":58,"title":["Distributed Minimum Cut Approximation"],"prefix":"10.1007","author":[{"given":"Mohsen","family":"Ghaffari","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: Proc. of the 31st Symp. on Princ. of Database Sys., PODS 2012, pp. 5\u201314 (2012)","DOI":"10.1145\/2213556.2213560"},{"key":"1_CR2","unstructured":"Censor-Hillel, K., Ghaffari, M., Kuhn, F.: A new perspective on vertex connectivity. arXiv (2013), \n                    \n                      http:\/\/arxiv.org\/abs\/1304.4553"},{"key":"1_CR3","unstructured":"Chattapodhyay, A., Pitassi, T.: The story of set disjointness. SIGACT News Complexity Theory Column\u00a067 (2011)"},{"issue":"5","key":"1_CR4","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. on Comp.\u00a041(5), 1235\u20131265 (2012)","journal-title":"SIAM J. on Comp."},{"key":"1_CR5","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1109\/TIT.1956.1056816","volume":"2","author":"P. Elias","year":"1956","unstructured":"Elias, P., Feinstein, A., Shannon, C.E.: Note on maximum flow through a network. IRE Transactions on Information Theory IT-2, 117\u2013199 (1956)","journal-title":"IRE Transactions on Information Theory IT-"},{"issue":"4","key":"1_CR6","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/1054916.1054931","volume":"35","author":"M. Elkin","year":"2004","unstructured":"Elkin, M.: Distributed approximation: a survey. SIGACT News\u00a035(4), 40\u201357 (2004)","journal-title":"SIGACT News"},{"key":"1_CR7","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton Univ. Press (2010)"},{"key":"1_CR8","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., Fulkersonn, D.R.: Maximal flow through a network. Canad. J. Math.\u00a08, 399\u2013404 (1956)","journal-title":"Canad. J. Math."},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: A matroid approach to finding edge connectivity and packing arborescences. In: Proc. 23rd ACM Symposium on Theory of Computing (STOC), pp. 112\u2013122 (1991)","DOI":"10.1145\/103418.103436"},{"key":"1_CR10","unstructured":"Ghaffari, M., Kuhn, F.: Distributed minimum cut approximation. arXiv (2013), \n                    \n                      http:\/\/arxiv.org\/abs\/1305.5520"},{"key":"1_CR11","unstructured":"Goel, A., Kapralov, M., Khanna, S.: Graph sparsification via refinement sampling. arXiv (2010), \n                    \n                      http:\/\/arxiv.org\/abs\/1004.4915"},{"issue":"4","key":"1_CR12","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B. Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math.\u00a05(4), 545\u2013557 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"1_CR13","unstructured":"Kapralov, M.: Personal communication (August 2013)"},{"key":"1_CR14","unstructured":"Karger, D.R.: Global min-cuts in \n                    \n                      \n                    \n                    $\\mathcal{RNC}$\n                  , and other ramifications of a simple min-out algorithm. In: Prc. 4th ACM-SIAM Symp. on Disc. Alg. (SODA), pp. 21\u201330 (1993)"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Karger, D.R.: Random sampling in cut, flow, and network design problems. In: Proc. 26th ACM Symposium on Theory of Computing (STOC), STOC 1994, pp. 648\u2013657 (1994)","DOI":"10.1145\/195058.195422"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Karger, D.R.: Random sampling in cut, flow, and network design problems. In: Proc. 26th ACM Symposium on Theory of Computing (STOC), pp. 648\u2013657 (1994)","DOI":"10.1145\/195058.195422"},{"key":"1_CR17","unstructured":"Karger, D.R.: Using randomized sparsification to approximate minimum cuts. In: Proc. 5th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 424\u2013432 (1994)"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Karger, D.R.: Minimum cuts in near-linear time. In: Proc. 28th ACM Symp. on Theory of Computing (STOC), pp. 56\u201363 (1996)","DOI":"10.1145\/237814.237829"},{"issue":"1","key":"1_CR19","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":"1_CR20","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: Proc. 25th ACM Symposium on Theory of Computing (STOC), pp. 757\u2013765 (1993)","DOI":"10.1145\/167088.167281"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Knuth, D.E.: Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms. AMS (1996)","DOI":"10.1090\/crmp\/010"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of k-dominating sets and applications. In: Proc. of the 14th Annual ACM Symp. on Principles of Dist. Comp., PODC 1995, pp. 238\u2013251 (1995)","DOI":"10.1145\/224964.224990"},{"key":"1_CR23","first-page":"118","volume":"7","author":"M.V. Lomonosov","year":"1971","unstructured":"Lomonosov, M.V., Polesskii, V.P.: Lower bound of network reliability. Problems of Information Transmission\u00a07, 118\u2013123 (1971)","journal-title":"Problems of Information Transmission"},{"key":"1_CR24","unstructured":"Matula, D.W.: A linear time 2\u2009+\u2009\u03b5 approximation algorithm for edge connectivity. In: Proc. of the 4th Annual ACM-SIAM Symposium on Disc. Alg., SODA 1993, pp. 500\u2013504 (1993)"},{"issue":"1","key":"1_CR25","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":"1_CR26","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"1_CR27","first-page":"19","volume":"20","author":"J.C. Picard","year":"1982","unstructured":"Picard, J.C., Queyranne, M.: Selected applications of minimum cuts in networks. Infor.\u00a020, 19\u201339 (1982)","journal-title":"Infor."},{"key":"1_CR28","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"A.A. Razborov","year":"1992","unstructured":"Razborov, A.A.: On the distributional complexity of disjointness. Theor. Comp. Sci.\u00a0106, 385\u2013390 (1992)","journal-title":"Theor. Comp. Sci."},{"issue":"1","key":"1_CR29","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. Journal of Algorithms\u00a023(1), 160\u2013179 (1997)","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-41527-2_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T18:36:07Z","timestamp":1558118167000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-41527-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642415265","9783642415272"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-41527-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}