{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T03:25:32Z","timestamp":1775791532058,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2022,12,6]],"date-time":"2022-12-06T00:00:00Z","timestamp":1670284800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,6]],"date-time":"2022-12-06T00:00:00Z","timestamp":1670284800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,8]]},"DOI":"10.1007\/s00453-022-01075-y","type":"journal-article","created":{"date-parts":[[2022,12,6]],"date-time":"2022-12-06T08:04:03Z","timestamp":1670313843000},"page":"2485-2514","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Algorithms for p-Faulty Search on a Half-Line"],"prefix":"10.1007","volume":"85","author":[{"given":"Anthony","family":"Bonato","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konstantinos","family":"Georgiou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Calum","family":"MacRury","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawe\u0142","family":"Pra\u0142at","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,6]]},"reference":[{"key":"1075_CR1","volume-title":"Search Problems","author":"R Ahlswede","year":"1987","unstructured":"Ahlswede, R., Wegener, I.: Search Problems. Wiley-Interscience, New York (1987)"},{"issue":"4","key":"1075_CR2","doi-asserted-by":"publisher","first-page":"1164","DOI":"10.1137\/S009753979732428X","volume":"29","author":"S Albers","year":"2000","unstructured":"Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164\u20131188 (2000)","journal-title":"SIAM J. Comput."},{"key":"1075_CR3","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/978-1-4614-6825-7_14","volume-title":"Search Theory: A Game Theoretic Perspective","year":"2013","unstructured":"Alpern, S., Fokkink, R., Gasieniec, L., Lindelauf, R., Subrahmanian, V. (eds.): Search Theory: A Game Theoretic Perspective, pp. 223\u2013230. Springer, New York (2013)"},{"key":"1075_CR4","volume-title":"The Theory of Search Games and Rendezvous","author":"S Alpern","year":"2003","unstructured":"Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. Springer, Berlin (2003)"},{"key":"1075_CR5","unstructured":"Angelopoulos, S.: Further connections between contract-scheduling and ray-searching problems. In: Q.Y. 0001, M.J. Wooldridge (eds.) Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25\u201331, 2015, pp. 1516\u20131522. AAAI Press (2015). http:\/\/ijcai.org\/proceedings\/2015"},{"key":"1075_CR6","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.dam.2019.01.039","volume":"260","author":"S Angelopoulos","year":"2019","unstructured":"Angelopoulos, S., D\u00fcrr, C., Lidbetter, T.: The expanding search ratio of a graph. Discrete Appl. Math. 260, 51\u201365 (2019)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"1075_CR7","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"R Baeza Yates","year":"1993","unstructured":"Baeza Yates, R., Culberson, J., Rawlins, G.: Searching in the plane. Inf. Comput. 106(2), 234\u2013252 (1993)","journal-title":"Inf. Comput."},{"issue":"4","key":"1075_CR8","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF02759737","volume":"2","author":"A Beck","year":"1964","unstructured":"Beck, A.: On the linear search problem. Israel J. Math. 2(4), 221\u2013228 (1964)","journal-title":"Israel J. Math."},{"issue":"3","key":"1075_CR9","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1137\/1005070","volume":"5","author":"R Bellman","year":"1963","unstructured":"Bellman, R.: An optimal search. SIAM Rev. 5(3), 274\u2013274 (1963)","journal-title":"SIAM Rev."},{"key":"1075_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2017.08.023","volume":"703","author":"P Bose","year":"2017","unstructured":"Bose, P., De Carufel, J.L.: A general framework for searching on a line. Theor. Comput. Sci. 703, 1\u201317 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"1075_CR11","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.tcs.2014.12.007","volume":"569","author":"P Bose","year":"2015","unstructured":"Bose, P., De Carufel, J.L., Durocher, S.: Searching on a line: a complete characterization of the optimal solution. Theor. Comput. Sci. 569, 24\u201342 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"1075_CR12","doi-asserted-by":"crossref","unstructured":"Brandt, S., Foerster, K.T., Richner, B., Wattenhofer, R.: Wireless evacuation on m rays with k searchers. In: SIROCCO, pp. 140\u2013157 (2017)","DOI":"10.1007\/978-3-319-72050-0_9"},{"key":"1075_CR13","doi-asserted-by":"crossref","unstructured":"Brandt, S., Laufenberg, F., Lv, Y., Stolz, D., Wattenhofer, R.: Collaboration without communication: evacuating two robots from a disk. In: CIAC, pp. 104\u2013115 (2017)","DOI":"10.1007\/978-3-319-57586-5_10"},{"key":"1075_CR14","unstructured":"Brandt, S., Uitto, J., Wattenhofer, R.: A tight lower bound for semi-synchronous collaborative grid exploration. In: DISC, pp. 13:1\u201313:17 (2018)"},{"issue":"3","key":"1075_CR15","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1109\/TRO.2004.839232","volume":"21","author":"W Burgard","year":"2005","unstructured":"Burgard, W., Moors, M., Stachniss, C., Schneider, F.E.: Coordinated multi-robot exploration. IEEE Trans. Robot. 21(3), 376\u2013386 (2005)","journal-title":"IEEE Trans. Robot."},{"issue":"11","key":"1075_CR16","doi-asserted-by":"publisher","first-page":"506","DOI":"10.3390\/info11110506","volume":"11","author":"H Chuangpishit","year":"2020","unstructured":"Chuangpishit, H., Georgiou, K., Sharma, P.: A multi-objective optimization problem on evacuating 2 robots from the disk in the face-to-face model; trade-offs between worst-case and average-case analysis. Information 11(11), 506 (2020)","journal-title":"Information"},{"key":"1075_CR17","doi-asserted-by":"crossref","unstructured":"Cohen, L., Emek, Y., Louidor, O., Uitto, J.: Exploring an infinite space with finite memory scouts. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 207\u2013224. SIAM (2017)","DOI":"10.1137\/1.9781611974782.14"},{"key":"1075_CR18","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Gasieniec, L., Gorry, T., Kranakis, E., Martin, R., Pajak, D.: Evacuating robots via unknown exit in a disk. In: F.\u00a0Kuhn (ed.) Distributed Computing\u201428th International Symposium, DISC 2014, Austin, TX, USA, October 12\u201315, 2014. Proceedings, Lecture Notes in Computer Science, vol. 8784, pp. 122\u2013136. Springer (2014)","DOI":"10.1007\/978-3-662-45174-8_9"},{"key":"1075_CR19","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.tcs.2020.11.014","volume":"852","author":"J Czyzowicz","year":"2020","unstructured":"Czyzowicz, J., Georgiou, K., Killick, R., Kranakis, E., Krizanc, D., Lafond, M., Narayanan, L., Opatrny, J., Shende, S.: Time-energy tradeoffs for evacuation by two robots in the wireless model. Theor. Comput. Sci. 852, 61\u201372 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"1075_CR20","unstructured":"Czyzowicz, J., Georgiou, K., Killick, R., Kranakis, E., Krizanc, D., Lafond, M., Narayanan, L., Opatrny, J., Shende, S.M.: Energy consumption of group search on a line. In: C.\u00a0Baier, I.\u00a0Chatzigiannakis, P.\u00a0Flocchini, S.\u00a0Leonardi (eds.) 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, LIPIcs, vol. 132, pp. 137:1\u2013137:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019). http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-109-2"},{"key":"1075_CR21","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1016\/j.tcs.2019.09.026","volume":"806","author":"J Czyzowicz","year":"2020","unstructured":"Czyzowicz, J., Georgiou, K., Killick, R., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S.: Priority evacuation from a disk: the case of n= 1, 2, 3. Theor. Comput. Sci. 806, 595\u2013616 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"1075_CR22","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.tcs.2020.09.023","volume":"846","author":"J Czyzowicz","year":"2020","unstructured":"Czyzowicz, J., Georgiou, K., Killick, R., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S.: Priority evacuation from a disk: The case of $$n\\ge 4$$. Theor. Comput. Sci. 846, 91\u2013102 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"1075_CR23","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-030-11072-7_14","volume-title":"Distributed Computing by Mobile Entities; Current Research in Moving and Computing","author":"J Czyzowicz","year":"2019","unstructured":"Czyzowicz, J., Georgiou, K., Kranakis, E.: Chapter 14: Group search and evacuation. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities; Current Research in Moving and Computing, pp. 335\u2013370. Springer, Berlin (2019)"},{"key":"1075_CR24","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, M.: Linear search with terrain-dependent speeds. In: CIAC, pp. 430\u2013441 (2017)","DOI":"10.1007\/978-3-319-57586-5_36"},{"key":"1075_CR25","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Kranakis, E., Krizanc, K., Narayanan, L., Opatrny, J., Shende, S.: Wireless autonomous robot evacuation from equilateral triangles and squares. In: ADHOCNOW, pp. 181\u2013194. Springer (2015)","DOI":"10.1007\/978-3-319-19662-6_13"},{"issue":"2","key":"1075_CR26","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.tcs.2006.05.018","volume":"361","author":"ED Demaine","year":"2006","unstructured":"Demaine, E.D., Fekete, S.P., Gal, S.: Online searching with turn cost. Theor. Comput. Sci. 361(2), 342\u2013355 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"1075_CR27","doi-asserted-by":"crossref","unstructured":"Feinerman, O., Korman, A., Lotker, Z., Sereni, J.S.: Collaborative search on the plane without communication. In: Proceedings of the 2012 ACM symposium on Principles of Distributed Computing, pp. 77\u201386 (2012)","DOI":"10.1145\/2332432.2332444"},{"issue":"3","key":"1075_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3304111","volume":"66","author":"P Fraigniaud","year":"2019","unstructured":"Fraigniaud, P., Korman, A., Rodeh, Y.: Parallel Bayesian search with no coordination. J. ACM 66(3), 1\u201328 (2019)","journal-title":"J. ACM"},{"key":"1075_CR29","volume-title":"Search Games","author":"S Gal","year":"1980","unstructured":"Gal, S.: Search Games. Academic Press, New York (1980)"},{"key":"1075_CR30","doi-asserted-by":"crossref","unstructured":"Gal, S.: Search Games. Wiley Encyclopedia for Operations Research and Management Science (2011)","DOI":"10.1002\/9780470400531.eorms0912"},{"key":"1075_CR31","unstructured":"Georgiou, K., Karakostas, G., Kranakis, E.: Search-and-fetch with 2 robots on a disk: wireless and face-to-face communication models. Discrete Math. Theor. Comput. Sci. 21(3) (2019). https:\/\/dmtcs.episciences.org\/5528"},{"key":"1075_CR32","doi-asserted-by":"crossref","unstructured":"Georgiou, K., Kranakis, E., Leonardos, N., Pagourtzis, A., Papaioannou, I.: Optimal cycle search despite the presence of faulty robots. In: 15th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS\u201919), Lecture Notes in Computer Science, to appear. Springer (2019)","DOI":"10.1007\/978-3-030-34405-4_11"},{"key":"1075_CR33","doi-asserted-by":"crossref","unstructured":"Georgiou, K., Lucier, J.: Weighted group search on a line. In: International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, pp. 124\u2013139. Springer (2020)","DOI":"10.1007\/978-3-030-62401-9_9"},{"issue":"11","key":"1075_CR34","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1016\/j.ipl.2009.01.020","volume":"109","author":"A Je\u017c","year":"2009","unstructured":"Je\u017c, A., \u0141opusza\u0144ski, J.: On the two-dimensional cow search problem. Inf. Process. Lett. 109(11), 543\u2013547 (2009)","journal-title":"Inf. Process. Lett."},{"key":"1075_CR35","doi-asserted-by":"publisher","DOI":"10.1201\/b18604","volume-title":"Search and Foraging: Individual Motion and Swarm Dynamics","author":"E Kagan","year":"2015","unstructured":"Kagan, E., Ben-Gal, I.: Search and Foraging: Individual Motion and Swarm Dynamics. CRC Press, Boca Raton (2015)"},{"issue":"1","key":"1075_CR36","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/inco.1996.0092","volume":"131","author":"MY Kao","year":"1996","unstructured":"Kao, M.Y., Reif, J.H., Tate, S.R.: Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Inf. Comput. 131(1), 63\u201379 (1996)","journal-title":"Inf. Comput."},{"key":"1075_CR37","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C., Yannakakis, M.: Searching a fixed graph. In: ICALP 96, pp. 280\u2013289. Springer (1996)","DOI":"10.1007\/3-540-61440-0_135"},{"key":"1075_CR38","doi-asserted-by":"crossref","unstructured":"Lamprou, I., Martin, R., Schewe, S.: Fast two-robot disk evacuation with wireless communication. In: DISC, pp. 1\u201315 (2016)","DOI":"10.1007\/978-3-662-53426-7_1"},{"key":"1075_CR39","doi-asserted-by":"crossref","unstructured":"Pattanayak, D., Ramesh, H., Mandal, P., Schmid, S.: Evacuating two robots from two unknown exits on the perimeter of a disk with wireless communication. In: ICDCN, pp. 20:1\u201320:4 (2018)","DOI":"10.1145\/3154273.3154313"},{"key":"1075_CR40","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected st-connectivity in log-space. In: STOC, pp. 376\u2013385 (2005)","DOI":"10.1145\/1060590.1060647"},{"key":"1075_CR41","volume-title":"Evolution and Optimum Seeking: The Sixth Generation","author":"HPP Schwefel","year":"1993","unstructured":"Schwefel, H.P.P.: Evolution and Optimum Seeking: The Sixth Generation. Wiley, Hoboken (1993)"},{"key":"1075_CR42","volume-title":"Theory of Optimal Search","author":"L Stone","year":"1975","unstructured":"Stone, L.: Theory of Optimal Search. Academic Press, New York (1975)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01075-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01075-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01075-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,7]],"date-time":"2023-08-07T12:02:50Z","timestamp":1691409770000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01075-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,6]]},"references-count":42,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["1075"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01075-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,6]]},"assertion":[{"value":"22 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}