{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,6]],"date-time":"2025-04-06T18:43:08Z","timestamp":1743964988819},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540755197"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75520-3_17","type":"book-chapter","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T03:46:33Z","timestamp":1189741593000},"page":"175-186","source":"Crossref","is-referenced-by-count":6,"title":["Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover"],"prefix":"10.1007","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]},{"given":"Raphael","family":"Yuster","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/BF01940874","volume":"16","author":"N. Alon","year":"1996","unstructured":"Alon, N., Naor, M.: Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica\u00a016, 434\u2013449 (1996)","journal-title":"Algorithmica"},{"key":"17_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1007\/BFb0032060","volume-title":"Automata, Languages and Programming","author":"N. Blum","year":"1990","unstructured":"Blum, N.: A New Approach to Maximum Matching in General Graphs. In: Paterson, M.S. (ed.) Automata, Languages and Programming. LNCS, vol.\u00a0443, pp. 586\u2013597. Springer, Heidelberg (1990)"},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"231","DOI":"10.2307\/2005828","volume":"28","author":"J. Bunch","year":"1974","unstructured":"Bunch, J., Hopcroft, J.: Triangular factorization and inversion by fast matrix multiplication. Mathematics of Computation\u00a028, 231\u2013236 (1974)","journal-title":"Mathematics of Computation"},{"key":"17_CR4","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1006\/jcom.1997.0438","volume":"13","author":"D. Coppersmith","year":"1997","unstructured":"Coppersmith, D.: Rectangular matrix multiplication revisited. Journal of Complexity\u00a013, 42\u201349 (1997)","journal-title":"Journal of Complexity"},{"key":"17_CR5","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation\u00a09, 251\u2013280 (1990)","journal-title":"Journal of Symbolic Computation"},{"key":"17_CR6","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. Canadian Journal of Mathematics\u00a017, 449\u2013467 (1965)","journal-title":"Canadian Journal of Mathematics"},{"issue":"4","key":"17_CR7","doi-asserted-by":"publisher","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. Journal of the ACM\u00a038(4), 815\u2013853 (1991)","journal-title":"Journal of the ACM"},{"key":"17_CR8","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1006\/jcss.1997.1385","volume":"54","author":"Z. Galil","year":"1997","unstructured":"Galil, Z., Margalit, O.: All Pairs Shortest Paths for graphs with small integer length edges. Journal of Computer and System Sciences\u00a054, 243\u2013254 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"Harvey, N.: Algebraic Structures and Algorithms for Matching and Matroid Problems. Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS), Berkeley, CA (October 2006)","DOI":"10.1109\/FOCS.2006.8"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1006\/jcom.1998.0476","volume":"14","author":"X. Huang","year":"1998","unstructured":"Huang, X., Pan, V.Y.: Fast rectangular matrix multiplications and applications. Journal of Complexity\u00a014, 257\u2013299 (1998)","journal-title":"Journal of Complexity"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Sharir, M., Verbin, E.: Colored intersection searching via sparse rectangular matrix multiplication. In: Proceedings of the 22nd ACM Symposium on Computational Geometry (SOCG), pp. 52\u201360 (2006)","DOI":"10.1145\/1137856.1137866"},{"key":"17_CR12","unstructured":"Lov\u00e1sz, L.: On determinants, matchings, and random algorithms. In: Fundamentals of computation theory, vol.\u00a02, pp. 565\u2013574. Akademie, Berlin (1979)"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $O(\\sqrt{|V|} \\cdot |E|)$ algorithm for finding maximum matching in general graphs. In: Proceedings of the 21st IEEE Symposium on Foundations of Computer Science (FOCS), pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"17_CR14","first-page":"248","volume-title":"FOCS","author":"M. Mucha","year":"2004","unstructured":"Mucha, M., Sankowski, P.: Maximum Matchings via Gaussian Elimination. In: FOCS. Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 248\u2013255. IEEE Computer Society Press, Los Alamitos (2004)"},{"issue":"4","key":"17_CR15","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast Probabilistic Algorithms for Verification of Polynomial Identities. Journal of the ACM\u00a027(4), 701\u2013717 (1980)","journal-title":"Journal of the ACM"},{"issue":"3","key":"17_CR16","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1995.1078","volume":"51","author":"R. Seidel","year":"1995","unstructured":"Seidel, R.: On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs. Journal of Computer and System Sciences\u00a051(3), 400\u2013403 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Shoshan, A., Zwick, U.: All pairs shortest paths in undirected graphs with integer weights. In: Proceedings of the 40th Symposium of Foundations of Computer Science (FOCS), pp. 605\u2013614 (1999)","DOI":"10.1109\/SFFCS.1999.814635"},{"key":"17_CR18","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"22","author":"W.T. Tutte","year":"1947","unstructured":"Tutte, W.T.: The factorization of linear graphs. Journal of the London Mathematical Society\u00a022, 107\u2013111 (1947)","journal-title":"Journal of the London Mathematical Society"},{"issue":"1","key":"17_CR19","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF01305952","volume":"14","author":"V.V. Vazirani","year":"1994","unstructured":"Vazirani, V.V.: A theory of alternating paths and blossoms for proving correctness of the $O(\\sqrt VE)$ general graph maximum matching algorithm. Combinatorica\u00a014(1), 71\u2013109 (1994)","journal-title":"Combinatorica"},{"issue":"1","key":"17_CR20","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic and Discrete Methods\u00a02(1), 77\u201379 (1981)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"17_CR21","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1077464.1077466","volume":"1","author":"R. Yuster","year":"2005","unstructured":"Yuster, R., Zwick, U.: Fast sparse matrix multiplication. ACM Transactions on Algorithms\u00a01, 2\u201313 (2005)","journal-title":"ACM Transactions on Algorithms"},{"key":"17_CR22","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0020-0190(76)90085-5","volume":"4","author":"G. Yuval","year":"1976","unstructured":"Yuval, G.: An algorithm for finding all shortest paths using N2.81 infinite-precision multiplications. Information Processing Letters\u00a04, 155\u2013156 (1976)","journal-title":"Information Processing Letters"},{"key":"17_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R. Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, K.W. (ed.) Symbolic and Algebraic Computation. LNCS, vol.\u00a072, pp. 216\u2013226. Springer, Heidelberg (1979)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75520-3_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:22:45Z","timestamp":1619518965000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75520-3_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540755197"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75520-3_17","relation":{},"subject":[]}}