{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T18:25:29Z","timestamp":1772043929226,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2018,8,22]],"date-time":"2018-08-22T00:00:00Z","timestamp":1534896000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P020372\/1"],"award-info":[{"award-number":["EP\/P020372\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P02002X\/1"],"award-info":[{"award-number":["EP\/P02002X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/L011018\/1"],"award-info":[{"award-number":["EP\/L011018\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2021296"],"award-info":[{"award-number":["2021296"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s00453-018-0501-y","type":"journal-article","created":{"date-parts":[[2018,8,22]],"date-time":"2018-08-22T13:05:56Z","timestamp":1534943156000},"page":"1757-1780","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Binary Search in Graphs Revisited"],"prefix":"10.1007","volume":"81","author":[{"given":"Argyrios","family":"Deligkas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George B.","family":"Mertzios","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,22]]},"reference":[{"issue":"6","key":"501_CR1","doi-asserted-by":"publisher","first-page":"2090","DOI":"10.1137\/S009753979731858X","volume":"28","author":"Y Ben-Asher","year":"1999","unstructured":"Ben-Asher, Y., Farchi, E., Newman, I.: Optimal search in trees. SIAM J. Comput. 28(6), 2090\u20132102 (1999)","journal-title":"SIAM J. Comput."},{"key":"501_CR2","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Hassidim, A.: The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well). In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, 25\u201328 Oct 2008, Philadelphia, PA, USA, pp. 221\u2013230 (2008)","DOI":"10.1109\/FOCS.2008.58"},{"key":"501_CR3","unstructured":"Boczkowski, L., Korman, A., Rodeh, Y.: Searching a tree with permanently noisy advice (2016). arXiv preprint arXiv:1611.01403"},{"key":"501_CR4","unstructured":"Boczkowski, L., Korman, A., Rodeh, Y.: Searching on trees with noisy memory (2016). CoRR, arXiv:1611.01403"},{"issue":"1","key":"501_CR5","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.tcs.2003.06.001","volume":"321","author":"R Carmo","year":"2004","unstructured":"Carmo, R., Donadelli, J., Kohayakawa, Y., Laber, E.S.: Searching in random partially ordered sets. Theor. Comput. Sci. 321(1), 41\u201357 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"50","key":"501_CR6","doi-asserted-by":"publisher","first-page":"6879","DOI":"10.1016\/j.tcs.2011.08.042","volume":"412","author":"F Cicalese","year":"2011","unstructured":"Cicalese, F., Jacobs, T., Laber, E.S., Molinaro, M.: On the complexity of searching in trees and partially ordered structures. Theor. Comput. Sci. 412(50), 6879\u20136896 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"501_CR7","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.tcs.2012.06.023","volume":"459","author":"F Cicalese","year":"2012","unstructured":"Cicalese, F., Jacobs, T., Laber, E.S., Valentim, C.D.: The binary identification problem for weighted trees. Theor. Comput. Sci. 459, 100\u2013112 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"13","key":"501_CR8","doi-asserted-by":"publisher","first-page":"2493","DOI":"10.1016\/j.dam.2008.03.007","volume":"156","author":"D Dereniowski","year":"2008","unstructured":"Dereniowski, D.: Edge ranking and searching in partial orders. Discrete Appl. Math. 156(13), 2493\u20132500 (2008)","journal-title":"Discrete Appl. Math."},{"key":"501_CR9","unstructured":"Dereniowski, D., Kosowski, A., Uznanski, P., Zou, M.: Approximation strategies for generalized binary search in weighted trees. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume\u00a080 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 84:1\u201384:14 (2017)"},{"key":"501_CR10","doi-asserted-by":"publisher","DOI":"10.1142\/1936","volume-title":"Combinatorial Group Testing and its Applications","author":"D Du","year":"1993","unstructured":"Du, D., Hwang, F.K.: Combinatorial Group Testing and its Applications. World Scientific, Singapore (1993)"},{"key":"501_CR11","unstructured":"Emamjomeh-Zadeh, E., Kempe, D.: A general framework for robust interactive learning. In: Advances in Neural Information Processing Systems, pp. 7082\u20137091 (2017)"},{"key":"501_CR12","doi-asserted-by":"crossref","unstructured":"Emamjomeh-Zadeh, E., Kempe, D.: Adaptive hierarchical clustering using ordinal queries. In: Proceedings of the Twenty-Ninth Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 415\u2013429. Society for Industrial and Applied Mathematics (2018)","DOI":"10.1137\/1.9781611975031.28"},{"key":"501_CR13","doi-asserted-by":"crossref","unstructured":"Emamjomeh-Zadeh, E., Kempe, D., Singhal, V.: Deterministic and probabilistic binary search in graphs. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, 18\u201321 June 2016, pp. 519\u2013532 (2016)","DOI":"10.1145\/2897518.2897656"},{"issue":"5","key":"501_CR14","doi-asserted-by":"publisher","first-page":"1001","DOI":"10.1137\/S0097539791195877","volume":"23","author":"U Feige","year":"1994","unstructured":"Feige, U., Raghavan, P., Peleg, D., Upfal, E.: Computing with noisy information. SIAM J. Comput. 23(5), 1001\u20131018 (1994)","journal-title":"SIAM J. Comput."},{"key":"501_CR15","doi-asserted-by":"publisher","first-page":"e20185","DOI":"10.7554\/eLife.20185","volume":"5","author":"E Fonio","year":"2016","unstructured":"Fonio, E., Heyman, Y., Boczkowski, L., Gelblum, A., Kosowski, A., Korman, A., Feinerman, O.: A locally-blazed ant trail achieves efficient collective navigation despite limited information. eLife 5, e20185 (2016)","journal-title":"eLife"},{"issue":"5","key":"501_CR16","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0020-0190(88)90194-9","volume":"28","author":"AV Iyer","year":"1988","unstructured":"Iyer, A.V., Ratliff, H.D., Vijayan, G.: Optimal node ranking of trees. Inf. Process. Lett. 28(5), 225\u2013229 (1988)","journal-title":"Inf. Process. Lett."},{"key":"501_CR17","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1515\/crll.1869.70.185","volume":"70","author":"C Jordan","year":"1869","unstructured":"Jordan, C.: Sur les assemblages de lignes. J. Reine Angew. Math. 70, 185\u2013190 (1869)","journal-title":"J. Reine Angew. Math."},{"key":"501_CR18","unstructured":"Laber, E.S., Milidi\u00fa, R.L., Pessoa, A.A.: On binary searching with non-uniform costs. In: Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 7\u20139 Jan 2001, Washington, DC, USA, pp. 855\u2013864 (2001)"},{"issue":"1","key":"501_CR19","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0166-218X(98)00029-8","volume":"85","author":"TW Lam","year":"1998","unstructured":"Lam, T.W., Yue, F.L.: Edge ranking of graphs is hard. Discrete Appl. Math. 85(1), 71\u201386 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"501_CR20","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/s004530010076","volume":"30","author":"TW Lam","year":"2001","unstructured":"Lam, T.W., Yue, F.L.: Optimal edge ranking of trees in linear time. Algorithmica 30(1), 12\u201333 (2001)","journal-title":"Algorithmica"},{"issue":"1","key":"501_CR21","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0196-6774(85)90020-3","volume":"6","author":"N Linial","year":"1985","unstructured":"Linial, N., Saks, M.E.: Searching ordered structures. J. Algorithms 6(1), 86\u2013103 (1985)","journal-title":"J. Algorithms"},{"key":"501_CR22","unstructured":"Mozes, S., Onak, K., Weimann, O.: Finding an optimal tree searching strategy in linear time. In: Proceedings of the Nineteenth Annual ACM\u2013SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, CA, USA, 20\u201322 Jan 2008, pp. 1096\u20131105 (2008)"},{"key":"501_CR23","volume-title":"Problem-Solving Methods in Artificial Intelligence","author":"NJ Nilsson","year":"1971","unstructured":"Nilsson, N.J.: Problem-Solving Methods in Artificial Intelligence. McGraw-Hill, New York (1971)"},{"key":"501_CR24","first-page":"1366","volume-title":"Advances in Neural Information Processing Systems","author":"R Nowak","year":"2009","unstructured":"Nowak, R.: Noisy generalized binary search. In: Bengio, Y., Schuurmans, D., Lafferty, J.D., Williams, C.K.I., Culotta, A. (eds.) Advances in Neural Information Processing Systems, vol. 22, pp. 1366\u20131374. Curran Associates, Hook (2009)"},{"key":"501_CR25","doi-asserted-by":"crossref","unstructured":"Onak, K., Parys, P.: Generalization of binary search: searching in trees and forest-like partial orders. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), Proceedings, 21\u201324 Oct 2006, Berkeley, CA, USA, pp. 379\u2013388 (2006)","DOI":"10.1109\/FOCS.2006.32"},{"key":"501_CR26","volume-title":"Heuristics\u2014Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Series in Artificial Intelligence","author":"J Pearl","year":"1984","unstructured":"Pearl, J.: Heuristics\u2014Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Series in Artificial Intelligence. Addison-Wesley, Boston (1984)"},{"issue":"1\u20132","key":"501_CR27","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0304-3975(01)00303-6","volume":"270","author":"A Pelc","year":"2002","unstructured":"Pelc, A.: Searching games with errors\u2014fifty years of coping with liars. Theor. Comput. Sci. 270(1\u20132), 71\u2013109 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"501_CR28","first-page":"505","volume":"6(B)","author":"A Renyi","year":"1961","unstructured":"Renyi, A.: On a problem in information theory. Magyar Tud. Akad. Mat. Kutato Int. Kozl 6(B), 505\u2013516 (1961)","journal-title":"Magyar Tud. Akad. Mat. Kutato Int. Kozl"},{"issue":"2","key":"501_CR29","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0020-0190(89)90161-0","volume":"33","author":"AA Sch\u00e4ffer","year":"1989","unstructured":"Sch\u00e4ffer, A.A.: Optimal node ranking of trees in linear time. Inf. Process. Lett. 33(2), 91\u201396 (1989)","journal-title":"Inf. Process. Lett."},{"key":"501_CR30","doi-asserted-by":"crossref","DOI":"10.1525\/9780520910553","volume-title":"Adventures of a Mathematician","author":"S Ulam","year":"1991","unstructured":"Ulam, S.: Adventures of a Mathematician. University of California Press, Berkeley (1991)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0501-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0501-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0501-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T13:21:31Z","timestamp":1720531291000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0501-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,22]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["501"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0501-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,22]]},"assertion":[{"value":"9 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}