{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T13:19:21Z","timestamp":1648819161202},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,7,4]],"date-time":"2007-07-04T00:00:00Z","timestamp":1183507200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,1]]},"DOI":"10.1007\/s00224-007-9018-5","type":"journal-article","created":{"date-parts":[[2007,7,3]],"date-time":"2007-07-03T15:52:01Z","timestamp":1183477921000},"page":"73-90","source":"Crossref","is-referenced-by-count":0,"title":["Processor Efficient Parallel Matching"],"prefix":"10.1007","volume":"42","author":[{"given":"Piotr","family":"Sankowski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,7,4]]},"reference":[{"key":"9018_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1007\/BFb0032060","volume-title":"Proc. 17th ICALP","author":"N. Blum","year":"1990","unstructured":"Blum, N.: A new approach to maximum matching in general graphs. In: Proc. 17th ICALP. Lecture Notes in Computer Science, vol. 443, pp. 586\u2013597. Springer, Berlin (1990)"},{"key":"9018_CR2","doi-asserted-by":"crossref","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. In: Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing, pp. 1\u20136. ACM Press (1987)","DOI":"10.1145\/28395.28396"},{"key":"9018_CR3","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J. Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees and flowers. Can. J. Math. 17, 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"issue":"4","key":"9018_CR4","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"H.N. Gabow","year":"1991","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph matching problems. J. ACM 38(4), 815\u2013853 (1991)","journal-title":"J. ACM"},{"issue":"2","key":"9018_CR5","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF02122800","volume":"8","author":"Z. Galil","year":"1988","unstructured":"Galil, Z., Pan, V.Y.: Improved processor bounds for combinatorial problems in RNC. Combinatorica 8(2), 189\u2013200 (1988)","journal-title":"Combinatorica"},{"key":"9018_CR6","volume-title":"The Theory of Matrices, vol. I, II","author":"F.R. Gantmacher","year":"1959","unstructured":"Gantmacher, F.R.: The Theory of Matrices, vol. I, II. Chelsea, New York (1959)"},{"issue":"5","key":"9018_CR7","doi-asserted-by":"crossref","first-page":"948","DOI":"10.1137\/S0097539793252687","volume":"24","author":"M. Giesbrecht","year":"1995","unstructured":"Giesbrecht, M.: Nearly optimal algorithms for canonical matrix forms. SIAM J. Comput. 24(5), 948\u2013969 (1995)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9018_CR8","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1137\/1020096","volume":"20","author":"D. Heller","year":"1978","unstructured":"Heller, D.: A survey of parallel algorithms in numerical linear algebra. SIAM Rev. 20(4), 740\u2013777 (1978)","journal-title":"SIAM Rev."},{"key":"9018_CR9","doi-asserted-by":"crossref","first-page":"706","DOI":"10.1137\/S003614459732076X","volume":"40","author":"S.-H. Hou","year":"1998","unstructured":"Hou, S.-H.: A simple proof of the Leverrier\u2013Faddeev characteristic polynomial algorithm. SIAM Rev. 40, 706\u2013709 (1998)","journal-title":"SIAM Rev."},{"key":"9018_CR10","doi-asserted-by":"crossref","unstructured":"Kaltofen, E., Pan, V.: Processor efficient parallel solution of linear systems over an abstract field. In: SPAA \u201991: Proceedings of the Third Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 180\u2013191. ACM Press (1991)","DOI":"10.1145\/113379.113396"},{"issue":"4","key":"9018_CR11","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02579264","volume":"6","author":"H.J. Karloff","year":"1986","unstructured":"Karloff, H.J.: A Las Vegas RNC algorithm for maximum matching. Combinatorica 6(4), 387\u2013391 (1986)","journal-title":"Combinatorica"},{"issue":"1","key":"9018_CR12","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02579407","volume":"6","author":"R.M. Karp","year":"1986","unstructured":"Karp, R.M., Upfal, E., Wigderson, A.: Constructing a perfect matching is in random NC. Combinatorica 6(1), 35\u201348 (1986)","journal-title":"Combinatorica"},{"key":"9018_CR13","unstructured":"Lov\u00e1sz, L.: On determinants, matchings and random algorithms. In: L. Budach (ed.) Fundamentals of Computation Theory, pp. 565\u2013574. Akademie (1979)"},{"key":"9018_CR14","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $O(\\sqrt{|V|}|E|)$ algorithm for finding maximum matching in general graphs. In: Proceedings of the Twenty First Annual IEEE Symposium on Foundations of Computer Science, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"issue":"5","key":"9018_CR15","doi-asserted-by":"crossref","first-page":"1002","DOI":"10.1137\/S0097539789162997","volume":"24","author":"G.L. Miller","year":"1995","unstructured":"Miller, G.L.: Flow in planar graphs with multiple sources and sinks. SIAM J. Comput. 24(5), 1002\u20131017 (1995)","journal-title":"SIAM J. Comput."},{"key":"9018_CR16","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 248\u2013255 (2004)","DOI":"10.1109\/FOCS.2004.40"},{"key":"9018_CR17","doi-asserted-by":"crossref","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. In: STOC \u201987: Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing, pp. 345\u2013354. ACM Press (1987)","DOI":"10.1145\/28395.383347"},{"key":"9018_CR18","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1016\/0196-6774(89)90005-9","volume":"10","author":"M.O. Rabin","year":"1989","unstructured":"Rabin, M.O., Vazirani, V.V.: Maximum matchings in general graphs through randomization. J. Algorithms 10, 557\u2013567 (1989)","journal-title":"J. Algorithms"},{"key":"9018_CR19","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. Schwartz","year":"1980","unstructured":"Schwartz, J.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27, 701\u2013717 (1980)","journal-title":"J. ACM"},{"issue":"3-4","key":"9018_CR20","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1016\/S0747-7171(03)00097-X","volume":"36","author":"A. Storjohann","year":"2003","unstructured":"Storjohann, A.: High-order lifting and integrality certification. J. Symb. Comput. 36(3-4), 613\u2013648 (2003)","journal-title":"J. Symb. Comput."},{"key":"9018_CR21","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"22","author":"T. Tutte","year":"1947","unstructured":"Tutte, T.: The factorization of linear graphs. J. Lond. Math. Soc. 22, 107\u2013111 (1947)","journal-title":"J. Lond. Math. Soc."},{"key":"9018_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"International Symposium on Symbolic and Algebraic Computation","author":"R. Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: International Symposium on Symbolic and Algebraic Computation. Lecture Notes in Computer Science, vol. 72, pp. 216\u2013226. Springer, Berlin (1979)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9018-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9018-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9018-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:34Z","timestamp":1558698694000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9018-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7,4]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["9018"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9018-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,7,4]]}}}