{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:46:57Z","timestamp":1725472017314},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540359043"},{"type":"electronic","value":"9783540359050"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_25","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T10:46:45Z","timestamp":1151491605000},"page":"274-285","source":"Crossref","is-referenced-by-count":11,"title":["Weighted Bipartite Matching in Matrix Multiplication Time"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Sankowski","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"25_CR1","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R. Bellman","year":"1958","unstructured":"Bellman, R.: On a Routing Problem. Quarterly of Applied Mathematics\u00a016(1), 87\u201390 (1958)","journal-title":"Quarterly of Applied Mathematics"},{"key":"25_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/28395.28396","volume-title":"Proceedings of the nineteenth annual ACM conference on Theory of computing","author":"D. Coppersmith","year":"1987","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, New York (1987)"},{"key":"25_CR3","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge Mass (1990)"},{"key":"25_CR4","first-page":"1324","volume":"10","author":"E.A. Dinic","year":"1969","unstructured":"Dinic, E.A., Kronrod, M.A.: An Algorithm for the Solution of the Assignment Problem. Soviet Math. Dokl.\u00a010, 1324\u20131326 (1969)","journal-title":"Soviet Math. Dokl."},{"issue":"2","key":"25_CR5","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. ACM\u00a019(2), 248\u2013264 (1972)","journal-title":"J. ACM"},{"key":"25_CR6","unstructured":"Eppstein, D.: Representing all Minimum Spanning Trees with Applications to Counting and Generation. Technical Report ICS-TR-95-50 (1995)"},{"issue":"2","key":"25_CR7","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/0022-0000(85)90039-X","volume":"31","author":"H.N. Gabow","year":"1985","unstructured":"Gabow, H.N.: Scaling Algorithms for Network Problems. J. Comput. Syst. Sci.\u00a031(2), 148\u2013168 (1985)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"25_CR8","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"H.N. Gabow","year":"1989","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster Scaling Algorithms for Network Problems. SIAM J. Comput.\u00a018(5), 1013\u20131036 (1989)","journal-title":"SIAM J. Comput."},{"key":"25_CR9","unstructured":"Goldberg, A.V.: Scaling algorithms for the shortest paths problem. In: SODA 1993: Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, pp. 222\u2013231 (1993)"},{"key":"25_CR10","first-page":"27","volume":"3","author":"M. Iri","year":"1960","unstructured":"Iri, M.: A new method for solving transportation-network problems. Journal of the Operations Research Society of Japan\u00a03, 27\u201387 (1960)","journal-title":"Journal of the Operations Research Society of Japan"},{"key":"25_CR11","unstructured":"Ford Jr., L.R.: Network Flow Theory. Paper P-923, The RAND Corperation, Santa Moncia, California (August 1956)"},{"key":"25_CR12","first-page":"438","volume-title":"Algorithms - ESA\u2019 99","author":"Ming-Yang Kao","year":"1999","unstructured":"Kao, M.-Y., Lam, T.W., Sung, W.-K., Ting, H.-F.: A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees. In: Proceedings of the 7th Annual European Symposium on Algorithms, pp. 438\u2013449 (1999)"},{"issue":"1","key":"25_CR13","doi-asserted-by":"publisher","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\u00a06(1), 35\u201348 (1986)","journal-title":"Combinatorica"},{"key":"25_CR14","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"H.W. Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly\u00a02, 83\u201397 (1955)","journal-title":"Naval Research Logistics Quarterly"},{"key":"25_CR15","unstructured":"Lov\u00e1sz, L.: On determinants, matchings and random algorithms. In: Budach, L. (ed.) Fundamentals of Computation Theory, pp. 565\u2013574. Akademie-Verlag (1979)"},{"key":"25_CR16","unstructured":"Moore, E.F.: The Shortest Path Through a Maze. In: Proceedings of the International Symposium on the Theory of Switching, pp. 285\u2013292. Harvard University Press (1959)"},{"key":"25_CR17","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":"25_CR18","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/28395.383347","volume-title":"STOC 1987: Proceedings of the nineteenth annual ACM conference on Theory of computing","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. In: STOC 1987: Proceedings of the nineteenth annual ACM conference on Theory of computing, pp. 345\u2013354. ACM Press, New York (1987)"},{"issue":"1","key":"25_CR19","first-page":"32","volume":"5","author":"J. Munkres","year":"1957","unstructured":"Munkres, J.: Algorithms for the Assignment and Transportation Problems. Journal of SIAM\u00a05(1), 32\u201338 (1957)","journal-title":"Journal of SIAM"},{"key":"25_CR20","doi-asserted-by":"publisher","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. Journal of Algorithms\u00a010, 557\u2013567 (1989)","journal-title":"Journal of Algorithms"},{"key":"25_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1007\/11561071_68","volume-title":"Algorithms \u2013 ESA 2005","author":"P. Sankowski","year":"2005","unstructured":"Sankowski, P.: Shortes paths in matrix multiplication time. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 770\u2013778. Springer, Heidelberg (2005)"},{"key":"25_CR22","doi-asserted-by":"publisher","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. Journal of the ACM\u00a027, 701\u2013717 (1980)","journal-title":"Journal of the ACM"},{"key":"25_CR23","first-page":"199","volume-title":"Proceedings of the Symposium on Information Networks","author":"A. Shimbel","year":"1955","unstructured":"Shimbel, A.: Structure in Communication Nets. In: Proceedings of the Symposium on Information Networks, pp. 199\u2013203. Polytechnic Press of the Polytechnic Institute of Brooklyn, Brooklyn (1955)"},{"issue":"3-4","key":"25_CR24","doi-asserted-by":"publisher","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.\u00a036(3-4), 613\u2013648 (2003)","journal-title":"J. Symb. Comput."},{"key":"25_CR25","first-page":"90","volume-title":"Proceedings of the 46th Annual Symposium on Foundations of Computer Science","author":"R. Yuster","year":"2005","unstructured":"Yuster, R., Zwick, U.: Answering distance queries in directed graphs using fast matrix multiplication. In: Proceedings of the 46th Annual Symposium on Foundations of Computer Science, pp. 90\u2013100. IEEE Computer Society Press, Los Alamitos (2005)"},{"key":"25_CR26","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.) EUROSAM 1979 and ISSAC 1979. LNCS, vol.\u00a072, pp. 216\u2013226. Springer, Heidelberg (1979)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:19:45Z","timestamp":1619507985000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/11786986_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}