{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T20:51:23Z","timestamp":1725742283054},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642400469"},{"type":"electronic","value":"9783642400476"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40047-6_66","type":"book-chapter","created":{"date-parts":[[2013,7,20]],"date-time":"2013-07-20T12:18:02Z","timestamp":1374322682000},"page":"659-670","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Efficient Parallel and External Matching"],"prefix":"10.1007","author":[{"given":"Marcel","family":"Birn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vitaly","family":"Osipov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Schulz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nodari","family":"Sitchinava","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"9","key":"66_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. Communications of the ACM\u00a031(9), 1116\u20131127 (1988)","journal-title":"Communications of the ACM"},{"key":"66_CR2","unstructured":"Birn, M.: Engineering fast parallel matching algorithms. Diploma Thesis, Karlsruhe Institute of Technology (2012)"},{"key":"66_CR3","doi-asserted-by":"crossref","unstructured":"Birn, M., Osipov, V., Sanders, P., Schulz, C., Sitchinava, N.: Efficient parallel and external matching. CoRR, abs\/1302.4587 (2013)","DOI":"10.1007\/978-3-642-40047-6_66"},{"key":"66_CR4","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Fineman, J.T., Shun, J.: Greedy sequential maximal independent set and matching are parallel on average. In: SPAA, pp. 308\u2013317 (2012)","DOI":"10.1145\/2312005.2312058"},{"key":"66_CR5","unstructured":"Chiang, Y.-J., Goodrich, M.T., Grove, E.F., Tamassia, R., Vengroff, D.E., Vitter, J.S.: External-memory graph algorithms. In: SODA, pp. 139\u2013149 (1995)"},{"key":"66_CR6","unstructured":"Davis, T.: The University of Florida Sparse Matrix Collection (2008), http:\/\/www.cise.ufl.edu\/research\/sparse\/matrices"},{"key":"66_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/978-3-540-45198-3_2","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"D.E. Drake","year":"2003","unstructured":"Drake, D.E., Hougardy, S.: Improved linear time approximation algorithms for weighted matchings. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) APPROX 2003+RANDOM 2003. LNCS, vol.\u00a02764, pp. 14\u201323. Springer, Heidelberg (2003)"},{"key":"66_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-642-30397-5_10","volume-title":"Facing the Multicore - Challenge II","author":"B.O. Fagginger Auer","year":"2012","unstructured":"Fagginger Auer, B.O., Bisseling, R.H.: A GPU algorithm for greedy graph matching. In: Keller, R., Kramer, D., Weiss, J.-P. (eds.) Facing Multicore-Challenge II 2011. LNCS, vol.\u00a07174, pp. 108\u2013119. Springer, Heidelberg (2012)"},{"key":"66_CR9","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: FOCS, pp. 285\u2013298 (1999)"},{"issue":"1","key":"66_CR10","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"V. Kumar","year":"1998","unstructured":"Kumar, V., Karypis, G.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing\u00a020(1), 359\u2013392 (1998)","journal-title":"SIAM Journal on Scientific Computing"},{"key":"66_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-642-25591-5_39","volume-title":"Algorithms and Computation","author":"M.T. Goodrich","year":"2011","unstructured":"Goodrich, M.T., Sitchinava, N., Zhang, Q.: Sorting, searching and simulation in the mapreduce framework. In: Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol.\u00a07074, pp. 374\u2013383. Springer, Heidelberg (2011)"},{"key":"66_CR12","unstructured":"Hoepman, J.-H.: Simple distributed weighted matchings. CoRR, cs.DC\/0410047 (2004)"},{"key":"66_CR13","doi-asserted-by":"crossref","unstructured":"Holtgrewe, M., Sanders, P., Schulz, C.: Engineering a Scalable High Quality Graph Partitioner, pp. 1\u201312 (2010)","DOI":"10.1109\/IPDPS.2010.5470485"},{"issue":"2","key":"66_CR14","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(86)90144-4","volume":"22","author":"A. Israeli","year":"1986","unstructured":"Israeli, A., Itai, A.: A fast and simple randomized parallel algorithm for maximal matching. Information Processing Letters\u00a022(2), 77\u201380 (1986)","journal-title":"Information Processing Letters"},{"key":"66_CR15","doi-asserted-by":"crossref","unstructured":"Karloff, H.J., Suri, S., Vassilvitskii, S.: A model of computation for mapreduce. In: SODA, pp. 938\u2013948 (2010)","DOI":"10.1137\/1.9781611973075.76"},{"key":"66_CR16","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Rytter, W.: Fast parallel algorithms for graph matching problems, vol.\u00a098. Clarendon Press (1998)","DOI":"10.1093\/oso\/9780198501626.001.0001"},{"issue":"4","key":"66_CR17","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing\u00a015(4), 1036\u20131053 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"66_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"708","DOI":"10.1007\/978-3-540-68111-3_74","volume-title":"Parallel Processing and Applied Mathematics","author":"F. Manne","year":"2008","unstructured":"Manne, F., Bisseling, R.H.: A parallel approximation algorithm for the weighted maximum matching problem. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Wasniewski, J. (eds.) PPAM 2007. LNCS, vol.\u00a04967, pp. 708\u2013717. Springer, Heidelberg (2008)"},{"key":"66_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/978-3-540-72845-0_19","volume-title":"Experimental Algorithms","author":"J. Maue","year":"2007","unstructured":"Maue, J., Sanders, P.: Engineering algorithms for approximate weighted matching. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol.\u00a04525, pp. 242\u2013255. Springer, Heidelberg (2007)"},{"key":"66_CR20","unstructured":"Mehlhorn, K., Sanders, P.: Algorithms and Data Structures \u2014 The Basic Toolbox. Springer (2008)"},{"key":"66_CR21","unstructured":"Merrill, D.: Back40computing: Fast and efficient software primitives for GPU computing, http:\/\/code.google.com\/p\/back40computing\/"},{"key":"66_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-642-11476-2_25","volume-title":"Structural Information and Communication Complexity","author":"M. Yves","year":"2010","unstructured":"Yves, M., Robson, J.M., Nasser, S.-D., Zemmari, A.: An optimal bit complexity randomized distributed MIS algorithm (Extended abstract). In: Kutten, S., \u017derovnik, J. (eds.) SIROCCO 2009. LNCS, vol.\u00a05869, pp. 323\u2013337. Springer, Heidelberg (2010)"},{"key":"66_CR23","doi-asserted-by":"crossref","unstructured":"Pettie, S., Sanders, P.: A simpler linear time 2\/3 \u2212 \u03b5 approximation for maximum weight matching. Technical Report MPI-I-2004-1-002, MPII (2004)","DOI":"10.1016\/j.ipl.2004.05.007"},{"key":"66_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/3-540-49116-3_24","volume-title":"STACS 99","author":"R. Preis","year":"1999","unstructured":"Preis, R.: Linear time $\\frac{1}{2}$ -approximation algorithm for maximum weighted matching in general graphs. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 259\u2013269. Springer, Heidelberg (1999)"},{"key":"66_CR25","doi-asserted-by":"crossref","unstructured":"Sanders, P., Schulz, C.: High Quality Graph Partitioning. In: Proceedings of the 10th DIMACS Implementation Challenge \u2013 Graph Partitioning and Graph Clustering, pp. 1\u201317. AMS (2013)","DOI":"10.1090\/conm\/588\/11700"}],"container-title":["Lecture Notes in Computer Science","Euro-Par 2013 Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40047-6_66","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,15]],"date-time":"2024-05-15T03:47:55Z","timestamp":1715744875000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40047-6_66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642400469","9783642400476"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40047-6_66","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}