{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:54:57Z","timestamp":1787507697817,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540323013","type":"print"},{"value":"9783540322887","type":"electronic"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11672142_13","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T03:27:54Z","timestamp":1141097274000},"page":"172-183","source":"Crossref","is-referenced-by-count":27,"title":["Quantum Algorithms for Matching and Network Flows"],"prefix":"10.1007","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"\u0160palek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L.R. Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Canadian Journal of Mathematics\u00a08, 399\u2013404 (1956)","journal-title":"Canadian Journal of Mathematics"},{"key":"13_CR2","first-page":"434","volume":"15","author":"A.V. Karzanov","year":"1974","unstructured":"Karzanov, A.V.: Determining the maximal flow in a network by the method of preflows. Soviet Mathematics Doklady\u00a015, 434\u2013437 (1974)","journal-title":"Soviet Mathematics Doklady"},{"key":"13_CR3","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0020-0190(78)90016-9","volume":"7","author":"V.M. Malhotra","year":"1978","unstructured":"Malhotra, V.M., Kumar, P., Maheshwari, S.N.: An O(V 3) algorithm for finding the maximum flows in networks. Information Processing Letters\u00a07, 277\u2013278 (1978)","journal-title":"Information Processing Letters"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Galil, Z., Naamad, A.: Network flow and generalized path compression. In: Proc. of 11th ACM STOC, pp. 13\u201326 (1979)","DOI":"10.1145\/800135.804394"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1145\/290179.290181","volume":"45","author":"A.V. Goldberg","year":"1998","unstructured":"Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. Journal of the ACM\u00a045, 783\u2013797 (1998)","journal-title":"Journal of the ACM"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S. Even","year":"1975","unstructured":"Even, S., Tarjan, R.E.: Network flow and testing graph connectivity. SIAM Journal on Computing\u00a04, 507\u2013518 (1975)","journal-title":"SIAM Journal on Computing"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Karger, D.R., Levine, M.S.: Finding maximum flows in undirected graphs seems easier than bipartite matching. In: Proc. of 30th ACM STOC, pp. 69\u201378 (1998)","DOI":"10.1145\/276698.276714"},{"key":"13_CR8","doi-asserted-by":"publisher","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"},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1145\/321941.321942","volume":"23","author":"H.N. Gabow","year":"1976","unstructured":"Gabow, H.N.: An efficient implementation of Edmonds\u2019 algorithm for maximum matching on graphs. Journal of the ACM\u00a023, 221\u2013234 (1976)","journal-title":"Journal of the ACM"},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing\u00a02, 225\u2013231 (1973)","journal-title":"SIAM Journal on Computing"},{"key":"13_CR11","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: Proc. of 21st IEEE FOCS, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: Proc. of 45th IEEE FOCS, pp. 248\u2013255 (2004)","DOI":"10.1109\/FOCS.2004.40"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proc. of 28th ACM STOC, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"13_CR14","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","volume":"46","author":"M. Boyer","year":"1998","unstructured":"Boyer, M., Brassard, G., H\u00f8yer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik\u00a046, 493\u2013505 (1998); Earlier version in Physcomp 1996","journal-title":"Fortschritte der Physik"},{"key":"13_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/978-3-540-27836-8_42","volume-title":"Automata, Languages and Programming","author":"C. D\u00fcrr","year":"2004","unstructured":"D\u00fcrr, C., Heiligman, M., H\u00f8yer, P., Mhalla, M.: Quatum query complexity of some graph problems. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 481\u2013493. Springer, Heidelberg (2004)"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Berzina, A., Dubrovsky, A., Freivalds, R., Lace, L., Scegulnaja, O.: Quantum query complexity for some graph problems. In: Proc. of 30th SOFSEM, pp. 140\u2013150 (2004)","DOI":"10.1007\/978-3-540-24618-3_11"},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.tcs.2005.01.019","volume":"339","author":"S. Zhang","year":"2004","unstructured":"Zhang, S.: On the power of Ambainis\u2019s lower bounds. ICALP 2004\u00a0339, 241\u2013256 (2004); Earlier version in ICALP 2004","journal-title":"Theoretical Computer Science"},{"key":"13_CR18","volume-title":"Quantum Computation and Quantum Information","author":"M.A. Nielsen","year":"2000","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: Quantum Computation and Quantum Information: A Millennium Volume. AMS Contemporary Mathematics Series, vol.\u00a0305, pp. 53\u201374 (2002)","DOI":"10.1090\/conm\/305\/05215"},{"key":"13_CR20","volume-title":"Network Flows","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice-Hall, Englewood Cliffs (1993)"},{"key":"13_CR21","first-page":"1277","volume":"11","author":"E.A. Dinic","year":"1970","unstructured":"Dinic, E.A.: Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Mathematics Doklady\u00a011, 1277\u20131280 (1970)","journal-title":"Soviet Mathematics Doklady"},{"key":"13_CR22","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 improvement in algorithmic efficiency for network flow problems. Journal of the ACM\u00a019, 248\u2013264 (1972)","journal-title":"Journal of the ACM"},{"key":"13_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S089548019733103X","volume":"12","author":"A.V. Goldberg","year":"1999","unstructured":"Goldberg, A.V., Rao, S.: Flows in undirected unit capacity networks. SIAM Journal on Discrete Mathematics\u00a012, 1\u20135 (1999)","journal-title":"SIAM Journal on Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","STACS 2006"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11672142_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T16:55:07Z","timestamp":1736268907000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11672142_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540323013","9783540322887"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/11672142_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}