{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:30:21Z","timestamp":1760707821817},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540678236"},{"type":"electronic","value":"9783540449294"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44929-9_7","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T09:20:53Z","timestamp":1178356853000},"page":"84-98","source":"Crossref","is-referenced-by-count":6,"title":["Parallel Approximation Algorithms for Maximum Weighted Matching in General Graphs"],"prefix":"10.1007","author":[{"given":"Ryuhei","family":"Uehara","sequence":"first","affiliation":[]},{"given":"Zhi -Zhong","family":"Chen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,24]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1002\/net.3230130404","volume":"13","author":"D. Avis","year":"1983","unstructured":"D. Avis. A Survey of Heuristics for the Weighted Matching Problem. Networks, 13:475\u2013493, 1983.","journal-title":"Networks"},{"key":"7_CR2","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds. Paths, Trees and Flowers. Canad. J. Math., 17:449\u2013467, 1965.","journal-title":"Canad. J. Math"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0020-0190(93)90055-E","volume":"46","author":"T. Fischer","year":"1993","unstructured":"T. Fischer, A.V. Goldberg, D.J. Haglin, and S. Plotkin. Approximating matchings in parallel. Information Processing Letters, 46:115\u2013118, 1993.","journal-title":"Information Processing Letters"},{"key":"7_CR4","unstructured":"H.N. Gabow. Data Structures for Weighted Matching and Nearest Common Ancestors with Linking. In Proc. 1st Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 434\u2013443. ACM, 1990."},{"issue":"1","key":"7_CR5","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/6462.6502","volume":"18","author":"Z. Galil","year":"1986","unstructured":"Z. Galil. Efficient Algorithms for Finding Maximum Matching in Graphs. Computing Surveys, 18(1):23\u201338, 1986.","journal-title":"Computing Surveys"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"R. Greenlaw, H.J. Hoover, and W.L. Ruzzo. Limits to Parallel Computation.. Oxford University Press, 1995.","DOI":"10.1093\/oso\/9780195085914.001.0001"},{"key":"7_CR7","unstructured":"F. Harary. Graph Theory. Addison-Wesley, 1972."},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0020-0190(86)90141-9","volume":"22","author":"A. Israeli","year":"1986","unstructured":"A. Israeli and Y. Shiloach. An Improved Parallel Algorithm for Maximal Matching. Information Processing Letters, 22:57\u201360, 1986.","journal-title":"Information Processing Letters"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"D.S. Johnson. A Catalog of Complexity Classes. In J. van Leeuwen, editor, The Handbook of Theoretical Computer Science, Vol. I: Algorithms and Complexity, pages 69\u2013161. Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"R.M. Karp and V. Ramachandran. Parallel Algorithms for Shared-Memory Machines. In J. van Leeuwen, editor, The Handbook of Theoretical Computer Science, Vol. I: Algorithms and Complexity, pages 870\u2013941. Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"7_CR11","unstructured":"M. Karpinski and W. Rytter. Fast Parallel Algorithms for Graph Matching Problems. Clarendon Press, 1998."},{"issue":"1","key":"7_CR12","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/BF02579407","volume":"6","author":"R.M. Karp","year":"1986","unstructured":"R.M. Karp, E. Upfal, and A. Wigderson. Constructing a Perfect Matching is in Random NCCombinatorica, 6(1):35\u201348, 1986.","journal-title":"Combinatorica"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/0022-0000(92)90024-D","volume":"44","author":"E.W. Mayr","year":"1992","unstructured":"E.W. Mayr and A. Subramanian. The Complexity of Circuit Value and Network Stability. Journal of Computer and System Science, 44:302\u2013323, 1992.","journal-title":"Journal of Computer and System Science"},{"key":"7_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/3-540-49116-3_24","volume-title":"STACS\u2019 99","author":"R. Preis","year":"1999","unstructured":"R. Preis. Linear Time 1\/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs. In STACS\u2019 99, pages 259\u2013269. Lecture Notes in Computer Science Vol. 1563, Springer-Verlag, 1999."},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0304-3975(87)90022-3","volume":"54","author":"S.M. Venkatesan","year":"1987","unstructured":"S.M. Venkatesan. Approximation Algorithms for Weighted Matching. Theoretical Computer Science, 54:129\u2013137, 1987.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44929-9_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T14:37:47Z","timestamp":1683815867000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44929-9_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540678236","9783540449294"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-44929-9_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}