{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:07:21Z","timestamp":1725664041235},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578994"},{"type":"electronic","value":"9783540483854"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57899-4_37","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:40:09Z","timestamp":1330263609000},"page":"11-20","source":"Crossref","is-referenced-by-count":0,"title":["Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality"],"prefix":"10.1007","author":[{"given":"N. W.","family":"Holloway","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Ravindran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. M.","family":"Gibbons","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0304-3975(88)90120-X","volume":"61","author":"E. Dahlhaus","year":"1988","unstructured":"E. Dahlhaus and M. Karpinski, \u201cParallel Construction of Perfect Matching and Hamiltonian Cycles on Dense Graphs\u201d, Theoretical computer science 61 (1988) 121\u2013136","journal-title":"Theoretical computer science"},{"key":"2_CR2","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"B","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, \u201cMatching and Polyhedrons with 0,1 Vertices\u201d, Journal of Research of the National Bureau of Standards B, 125\u2013130 (1965).","journal-title":"Journal of Research of the National Bureau of Standards"},{"key":"2_CR3","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, \u201cPaths, trees and flowers\u201d, Canadian Journal of Mathematics 17 (1965) 449\u201367.","journal-title":"Canadian Journal of Mathematics"},{"key":"2_CR4","unstructured":"H.N. Gabow, \u201cImplementations of Algorithm for Maximum Matching on Nonbiparitte Graphs\u201d, Ph.D. Dissertation, Dept. of Computer Science, Stanford University, 1974."},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"D.Y. Grigoriev and M. Karpinski, \u201cThe Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents is in NC\u201d, Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (1987), 166\u2013172.","DOI":"10.1109\/SFCS.1987.56"},{"key":"2_CR6","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF02122800","volume":"8","author":"Z. Galil","year":"1988","unstructured":"Z. Galil and V. Pan, \u201cImproved Processor Bounds for Combinatorial Problems in RNC\u201d, Combinatorica 8 (1988) 189\u2013200.","journal-title":"Combinatorica"},{"key":"2_CR7","unstructured":"A.M. Gibbons, Algorithmic Graph Theory, Cambridge University Press (1985)."},{"key":"2_CR8","unstructured":"A.M. Gibbons and W. Rytter, Efficient Parallel Algorithms, Cambridge University Press (1988)."},{"key":"2_CR9","unstructured":"A.M. Gibbons and P.G. Spirakis (eds), Lectures on Parallel Computation, Cambridge University Press (1993)."},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"D. Hembold and E. Mayer, \u201cTwo-processor Scheduling is in NC\u201d, VLSI Algorithm and Architectures, editors: Makedon et al., Lecture Notes in Computer Science, Vol. 227 (1986) 12\u201325.","DOI":"10.1007\/3-540-16766-8_2"},{"key":"2_CR11","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/0020-0190(81)90103-4","volume":"12","author":"M. Iri","year":"1981","unstructured":"M. Iri, K. Murota and S. Matsui, \u201cLinear-time Approximation Algorithms for Finding the Minimum-Weight Perfect Matching on a Plane\u201d, Information Processing Letters 12 (1981) 206\u2013209.","journal-title":"Information Processing Letters"},{"key":"2_CR12","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0020-0190(86)90141-9","volume":"33","author":"A. Israeli","year":"1986","unstructured":"A. Israeli and Y. Shiloach, \u201cAn improved algorithm for maximal matching\u201d, Information Processing Letters\u201d 33 (1986) 57\u201360.","journal-title":"Information Processing Letters"},{"key":"2_CR13","unstructured":"D.B. Johnson and P. Metaxas, \u201cConnected components in O(log3\/2 \u00a6V\u00a6) parallel time for the CREW PRAM\u201d, FOCS, 1991"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"D.R. Karger, N. Nisan and M. Parnas, \u201cFast Connected Components Algorithms for the EREW PRAM\u201d, 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 373\u2013381 (1992)","DOI":"10.1145\/140901.141920"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"R. Karp and V. Ramachandran, \u201cParallel algorithms for Shared Memory Machines\u201d, Handbook of Theoretical Computer Science, J. van Leeuwen (editor), vol.1, Elsevier and MIT Press (1991).","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"R. Karp, E. Upfal and A. Wigderson, \u201cConstructing a Perfect Matching is in Random NC\u201d, Proceedings of the Annual ACM Symposium on Theory of Computing (1985), 22\u201332.","DOI":"10.1145\/22145.22148"},{"key":"2_CR17","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0020-0190(82)90093-X","volume":"14","author":"L. Kucera","year":"1982","unstructured":"L. Kucera, \u201cParallel computation and conflicts in memory access\u201d, Information Processing Letters, Vol. 14, (1982) 93\u201396","journal-title":"Information Processing Letters"},{"key":"2_CR18","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. L. Lawler","year":"1976","unstructured":"E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt-Rinehart-Winston, New York, 1976."},{"key":"2_CR19","volume-title":"Introduction to Parallel Algorithms and Achitectures: Arrays \u2022 Trees \u2022 Hypercubes","author":"F. T. Leighton","year":"1992","unstructured":"F. Thomson Leighton, Introduction to Parallel Algorithms and Achitectures: Arrays \u2022 Trees \u2022 Hypercubes, Morgan Kaufmann, California (1992)."},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"K. Mulmuley, U. Vazirani and V. Vazirani, \u201cMatching is as Easy as Matrix Inverson\u201d, Proceedings of the Annual ACM Symposium on Theory of Computing (1987), 345\u2013354.","DOI":"10.1145\/28395.383347"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"J. Naor, \u201cComputing a Perfect Matching in a Line Graph\u201d, Proceedings of the 9 th Conference on the Foundations of Software Technology and Theoretical Computer Science, (1989) 139\u2013148.","DOI":"10.1007\/BFb0040382"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"C.N.K. Osiakwan and S.G. Akl, \u201cThe Maximum weight perfect matching problem for complete weighted graphs is in PC\u201d, Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing (1990) 880\u2013887.","DOI":"10.1109\/SPDP.1990.143503"},{"key":"2_CR23","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0196-6774(84)90024-5","volume":"5","author":"D. A. Plaisted","year":"1984","unstructured":"D.A. Plaisted, \u201cHeuristic Matching for Graphs Satisfying the Triangle Inequality\u201d, Journal of Algorithms 5 (1984) 163\u2013179.","journal-title":"Journal of Algorithms"},{"key":"2_CR24","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1137\/0210050","volume":"10","author":"E. M. Reingold","year":"1981","unstructured":"E.M. Reingold and R.E. Tarjan, \u201cIn a greedy Heuristic for Complete Matching\u201d, SIAM Journal of Computing 10 (1981) 676\u2013681.","journal-title":"SIAM Journal of Computing"},{"key":"2_CR25","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Y. Shiloach and U. Vishkin, \u201cAn O(log n) parallel connectivity algorithm\u201d, Journal of Algorithms, Vol. 3, (1982) 57\u201367.","journal-title":"Journal of Algorithms"},{"key":"2_CR26","doi-asserted-by":"crossref","unstructured":"K.J. Supowit, D.A. Plaisted and E.M. Reingold, \u201cHeuristics for Weighted Perfect Matching\u201d, Proceedings of the Annual ACM Symposium on Theory of Computing, (1980) 398\u2013419.","DOI":"10.1145\/800141.804689"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"R.E. Tarjan and U. Vishkin, \u201cFinding biconnected components and computing tree functions in logarithmic parallel time\u201d, Proceedings of the 25 th Annual IEEE Symposium on the Foundations of Computer Science, (1984), 12\u201320, also SIAM Journal of Computing, 14, 4(1985) 862\u201374.","DOI":"10.1109\/SFCS.1984.715896"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57899-4_37.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:15:42Z","timestamp":1605647742000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57899-4_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578994","9783540483854"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-57899-4_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}