{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T05:09:49Z","timestamp":1736485789222,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540642756"},{"type":"electronic","value":"9783540697152"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054332","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T05:37:37Z","timestamp":1149658657000},"page":"316-330","source":"Crossref","is-referenced-by-count":2,"title":["Communication-efficient parallel multiway and approximate minimum cut computation"],"prefix":"10.1007","author":[{"given":"Friedhelm Meyer","family":"auf der Heide","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriel Ter\u00e1n","family":"Martinez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,25]]},"reference":[{"key":"28_CR1","first-page":"129","volume":"95","author":"M. Adler","year":"1995","unstructured":"M. Adler, J. W. Byers, R. M. Karp, Parallel sorting with limited bandwidth, SPAA 95, pages 129\u2013136, 1995.","journal-title":"SPAA"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"A. B\u00e4umker, W. Dittrich, and F. Meyer auf der Heide, Truly efficient parallel algorithms: 1-optimal multisearch for an extension of the BSP model, ESA 95, 1995.","DOI":"10.1007\/3-540-60313-1_131"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"E. C\u00e1ceres, F. Dehne, A. Ferreira, P. Flocchini, I. Rieping, A. Roncato, N.Santoro, S. W. Song, Efficient parallel graph algorithms for coarse grained multicomputers and BSP, ICALP 97, Bologna, Italy, 1997.","DOI":"10.1007\/3-540-63165-8_195"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"D. E. Culler, R. M. Karp, D. A. Peterson, A. Sahay, K. E. Schauser, E. Santos, R.Subramonian, T. von Eicken, Log P: Towards a realistic model of parallel computation, in Proc. 4th ACM SIGPLAN Symp. on Princ. and Practice of Parallel Programming, pages 1\u201312, 1993.","DOI":"10.1145\/173284.155333"},{"key":"28_CR5","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1006\/jpdc.1994.1085","volume":"22","author":"A. V. Gerbessiotis","year":"1994","unstructured":"A. V. Gerbessiotis L. G. Valiant, Direct bulk-synchronous parallel algorithms, J. of Parallel and Distributed Computing, 22:251\u2013267, 1994.","journal-title":"J. of Parallel and Distributed Computing"},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"M. T. Goodrich, Communication-efficient parallel sorting, STOC 96, 1996.","DOI":"10.1145\/237814.237870"},{"key":"28_CR7","unstructured":"M. T. Goodrich, Randomized fully-scalable BSP techniques for multisearching and convex hull construction, SODA 97, 1997."},{"key":"28_CR8","volume-title":"An Introduction to Parallel Algorithms","author":"J. J\u00e1j\u00e1","year":"1992","unstructured":"J. J\u00e1j\u00e1, An Introduction to Parallel Algorithms, Addison-Wesley, Reading, Mass., 1992."},{"key":"28_CR9","unstructured":"D. R. Karger, Global min-cuts in RNC and other ramifications of a simple mincut algorithm, SODA 93, pages 21\u201330, 1993."},{"key":"28_CR10","unstructured":"D. R. Karger, Random Sampling in Graph Optimization Problems, PhD thesis, Stanford University, 1994."},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"D. R. Karger, Minimum cuts in near-linear time, STOC 96, pages 56\u201363, 996.","DOI":"10.1145\/237814.237829"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"D. R. Karger, A randomized fully polynomial approximation scheme for the all terminal network reliability problem, STOC 95, pages 11\u201317, 1995.","DOI":"10.1145\/225058.225069"},{"issue":"4","key":"28_CR13","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"D. R. Karger","year":"1996","unstructured":"D. R. Karger, C. Stein, A new approach to the minimum cut problem, Journal of the ACM, 43(4):601\u2013640, 1996.","journal-title":"Journal of the ACM"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"Y. Mansour, N. Nisan, U. Vishkin, Trade-offs between communication throughput and parallel time STOC 94, pages 372\u2013381, 1994.","DOI":"10.1145\/195058.195199"},{"key":"28_CR15","unstructured":"D. W. Matula, A linear 2+\u03b5 approximation algorithm for edge connectivity, SODA 93, pages 500\u2013504, 1993."},{"key":"28_CR16","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0405004","volume":"5","author":"H. Nagamochi","year":"1992","unstructured":"H. Nagamochi, T. Ibaraki, Computing edge connectivity in multigraphs and capacitated graphs, SIAM J. of Discrete Mathematics, 5:54\u201366, 1992.","journal-title":"SIAM J. of Discrete Mathematics"},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou, M. Yannakakis, Towards an architecture-independent analysis of parallel algorithms, STOC 98, pages 510\u2013513, 1988.","DOI":"10.1145\/62212.62262"},{"key":"28_CR18","volume-title":"Synthesis or Parallel Algorithms","author":"J. H. Reif","year":"1993","unstructured":"J. H. Reif, Synthesis or Parallel Algorithms, Morgan Kaufmann Publishers, Inc., San Mateo, CA, 1993."},{"key":"28_CR19","doi-asserted-by":"crossref","unstructured":"M. Stoer, F. Wagner, A simple min cut algorithm, ESA 94, page 141\u2013147, 1994.","DOI":"10.1007\/BFb0049404"},{"key":"28_CR20","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"L. G. Valiant","year":"1990","unstructured":"L. G. Valiant, A bridging model for parallel computation, Comm. ACM,33:103\u2013lll, 1990.","journal-title":"Comm. ACM"}],"container-title":["Lecture Notes in Computer Science","LATIN'98: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054332","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T07:11:57Z","timestamp":1736406717000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0054332"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540642756","9783540697152"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0054332","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}