{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T06:32:54Z","timestamp":1774593174676,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_42","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T22:53:21Z","timestamp":1284591201000},"page":"481-493","source":"Crossref","is-referenced-by-count":36,"title":["Quantum Query Complexity of Some Graph Problems"],"prefix":"10.1007","author":[{"given":"Christoph","family":"D\u00fcrr","sequence":"first","affiliation":[]},{"given":"Mark","family":"Heiligman","sequence":"additional","affiliation":[]},{"given":"Peter","family":"H\u00f8yer","sequence":"additional","affiliation":[]},{"given":"Mehdi","family":"Mhalla","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"42_CR1","doi-asserted-by":"crossref","unstructured":"Aharonov, A., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proceedings of 33th Annual ACM Symposium on Theory of Computing (STOC), pp. 50\u201359 (2001)","DOI":"10.1145\/380752.380758"},{"key":"42_CR2","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1006\/jcss.2002.1826","volume":"64","author":"A. Ambainis","year":"2002","unstructured":"Ambainis, A.: Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences\u00a064, 750\u2013767 (2002)","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"42_CR3","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/S0097539796300933","volume":"26","author":"C.H. Bennett","year":"1997","unstructured":"Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM Journal on Computing\u00a026(5), 1510\u20131523 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"42_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-540-24618-3_11","volume-title":"SOFSEM 2004: Theory and Practice of Computer Science","author":"A. Berzina","year":"2004","unstructured":"Berzina, A., Dubrovsky, A., Freivalds, R., Lace, L., Scegulnaja, O.: Quantum Query Complexity for Some Graph Problems. In: Van Emde Boas, P., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2004. LNCS, vol.\u00a02932, pp. 140\u2013150. Springer, Heidelberg (2004)"},{"key":"42_CR5","first-page":"37","volume":"3","author":"O. Bor\u016fvka","year":"1926","unstructured":"Bor\u016fvka, O.: O jistem problemu minimaln im. Prace Mor. Prrodove Spol. v Brne (Acta Societ. Scient. Natur. Moravicae)\u00a03, 37\u201358 (1926)","journal-title":"Prace Mor. Prrodove Spol. v Brne (Acta Societ. Scient. Natur. Moravicae)"},{"issue":"4-5","key":"42_CR6","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(4-5), 493\u2013505 (1998)","journal-title":"Fortschritte Der Physik"},{"key":"42_CR7","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P.: An exact quantum polynomial-time algorithm for Simon\u2019s problem. In: Proceedings of Fifth Israeli Symposium on Theory of Computing and Systems (ISTCS), pp. 12\u201323 (1997)","DOI":"10.1109\/ISTCS.1997.595153"},{"key":"42_CR8","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"},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., de Wolf, R.: Ch. Zalka, Bounds for Small-Error and Zero-Error Quantum Algorithms. In: 40th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 358\u2013368 (1999)","DOI":"10.1109\/SFFCS.1999.814607"},{"key":"42_CR10","doi-asserted-by":"crossref","unstructured":"Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D.A.: Exponential algorithmic speedup by quantum walk. In: Proceedings of 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 59\u201368 (2003)","DOI":"10.1145\/780542.780552"},{"key":"42_CR11","unstructured":"D\u00fcrr, C., H\u00f8yer, P.: A quantum algorithm for finding the minimum. quantph\/9607014 (1996)"},{"key":"42_CR12","doi-asserted-by":"crossref","unstructured":"Fahri, E., Goldstone, J., Gutmann, S., Sipser, M.: A limit on the speed of quantum computation in determining parity. quant-ph\/9802045 (1998)","DOI":"10.1103\/PhysRevLett.81.5442"},{"key":"42_CR13","doi-asserted-by":"crossref","unstructured":"Grover, L.: A fast mechanical algorithm for database search. In: Proceedings of 28th Annual ACM Symposium on Theory of Computing (STOC), pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"42_CR14","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/PL00009228","volume":"22","author":"M.R. Henzinger","year":"1998","unstructured":"Henzinger, M.R., Fredman, M.L.: Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica\u00a022, 351\u2013362 (1998)","journal-title":"Algorithmica"},{"issue":"4","key":"42_CR15","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1080\/00107151031000110776","volume":"44","author":"J. Kempe","year":"2003","unstructured":"Kempe, J.: Quantum random walks\u2014an introductory overview. Contemporary Physics\u00a044(4), 307\u2013327 (2003)","journal-title":"Contemporary Physics"},{"key":"42_CR16","volume-title":"The Design and Analysis of Algorithms","author":"D. Kozen","year":"1991","unstructured":"Kozen, D.: The Design and Analysis of Algorithms. Springer, Heidelberg (1991)"},{"key":"42_CR17","doi-asserted-by":"crossref","unstructured":"Kruskal Jr., J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society (1956)","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"42_CR18","unstructured":"Nayak, A.: Lower Bounds for Quantum Computation and Communication, PhD from the University of California, Berkeley (1999)"},{"key":"42_CR19","doi-asserted-by":"crossref","unstructured":"Nayak, A., Wu, F.: The quantum query complexity of approximating the median and related statistics. In: Proceedings of 31th Annual ACM Symposium on Theory of Computing (STOC), pp. 384\u2013393 (1999)","DOI":"10.1145\/301250.301349"},{"key":"42_CR20","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0012-365X(00)00224-7","volume":"233","author":"J. Nesetril","year":"2001","unstructured":"Nesetril, J., Milkov\u00e1, E., Nesetrilov\u00e1, H.: Otakar Bor\u016fvka on Minimum Spanning Tree Problem: translation of both the 1926 papers, comments, history. Discrete Mathematics\u00a0233, 3\u201336 (2001)","journal-title":"Discrete Mathematics"},{"key":"42_CR21","doi-asserted-by":"crossref","unstructured":"Prim, R.: Shortest connecting networks and some generalizations. Bell Syst. Tech. J (1957)","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"issue":"2","key":"42_CR22","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1006\/jcss.2000.1732","volume":"62","author":"J. Watrous","year":"2001","unstructured":"Watrous, J.: Quantum simulations of classical random walks and undirected graph connectivity. Journal of Computer and System Sciences\u00a062(2), 376\u2013391 (2001)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T21:30:26Z","timestamp":1740519026000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}