{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T04:26:10Z","timestamp":1768451170043,"version":"3.49.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,5,7]],"date-time":"2018-05-07T00:00:00Z","timestamp":1525651200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"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"}]},{"DOI":"10.13039\/501100006251","name":"Universit\u00e9 de Bordeaux","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006251","id-type":"DOI","asserted-by":"publisher"}]},{"name":"University of Liverpool initiative Networks Systems and Technologies NeST"},{"name":"ANR projects Macaron","award":["ANR- 13-JS02-002"],"award-info":[{"award-number":["ANR- 13-JS02-002"]}]},{"name":"ANR projects Descartes","award":["ANR-16-CE40-0023"],"award-info":[{"award-number":["ANR-16-CE40-0023"]}]},{"name":"\u201cInvestments for the future\u201d Programme IdEx Bordeaux-CPU","award":["ANR- 10-IDEX-03-02"],"award-info":[{"award-number":["ANR- 10-IDEX-03-02"]}]},{"name":"ANR project Displexity","award":["ANR-11- BS02-014"],"award-info":[{"award-number":["ANR-11- BS02-014"]}]},{"name":"National Science Centre, Poland","award":["2015\/17\/B\/ST6\/01897"],"award-info":[{"award-number":["2015\/17\/B\/ST6\/01897"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,1]]},"DOI":"10.1007\/s00453-018-0447-0","type":"journal-article","created":{"date-parts":[[2018,5,7]],"date-time":"2018-05-07T12:44:49Z","timestamp":1525697089000},"page":"317-342","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Linear Search by a Pair of Distinct-Speed Robots"],"prefix":"10.1007","volume":"81","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1496-9299","authenticated-orcid":false,"given":"Evangelos","family":"Bampas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jurek","family":"Czyzowicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leszek","family":"G\u0105sieniec","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Ilcinkas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2477-1702","authenticated-orcid":false,"given":"Tomasz","family":"Kociumaka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominik","family":"Paj\u0105k","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,5,7]]},"reference":[{"key":"447_CR1","doi-asserted-by":"crossref","unstructured":"Alpern, S., Fokkink, R., Gasieniec, L., Lindelauf, R., Subrahmanian, V. (eds.): Search Theory\u2014A Game Theoretic Perspective. Springer, New York (2013)","DOI":"10.1007\/978-1-4614-6825-7"},{"key":"447_CR2","series-title":"International Series in Operations Research & Management Science","volume-title":"The Theory of Search Games and Rendezvous","author":"S Alpern","year":"2002","unstructured":"Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. International Series in Operations Research & Management Science, vol. 55. Kluwer Academic, New York (2002)"},{"key":"447_CR3","doi-asserted-by":"publisher","unstructured":"Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching with uncertainty (extended abstract). In: Karlsson, R.G., Lingas, A. (eds.) Scandinavian Workshop on Algorithm Theory, SWAT 1988, LNCS, vol. 318, pp. 176\u2013189. Springer (1988). \n                    https:\/\/doi.org\/10.1007\/3-540-19487-8_20","DOI":"10.1007\/3-540-19487-8_20"},{"issue":"2","key":"447_CR4","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"RA Baeza-Yates","year":"1993","unstructured":"Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching in the plane. Inf. Comput. 106(2), 234\u2013252 (1993). \n                    https:\/\/doi.org\/10.1006\/inco.1993.1054","journal-title":"Inf. Comput."},{"key":"447_CR5","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0925-7721(95)00003-R","volume":"5","author":"RA Baeza-Yates","year":"1995","unstructured":"Baeza-Yates, R.A., Schott, R.: Parallel searching in the plane. Comput. Geom. 5, 143\u2013154 (1995). \n                    https:\/\/doi.org\/10.1016\/0925-7721(95)00003-R","journal-title":"Comput. Geom."},{"key":"447_CR6","unstructured":"Barajas, J., Serra, O.: The lonely runner with seven runners. Electr. J. Comb. 15(1) (2008). \n                    http:\/\/www.combinatorics.org\/Volume_15\/Abstracts\/v15i1r48.html"},{"issue":"4","key":"447_CR7","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). \n                    https:\/\/doi.org\/10.1007\/BF02759737","journal-title":"Israel J. Math."},{"issue":"3","key":"447_CR8","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). \n                    https:\/\/doi.org\/10.1137\/1005070","journal-title":"SIAM Rev."},{"issue":"1","key":"447_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.2001.3081","volume":"176","author":"MA Bender","year":"2002","unstructured":"Bender, M.A., Fern\u00e1ndez, A., Ron, D., Sahai, A., Vadhan, S.P.: The power of a pebble: exploring and mapping directed graphs. Inf. Comput. 176(1), 1\u201321 (2002). \n                    https:\/\/doi.org\/10.1006\/inco.2001.3081","journal-title":"Inf. Comput."},{"key":"447_CR10","doi-asserted-by":"publisher","unstructured":"Bender, M.A., Slonim, D.K.: The power of team exploration: two robots can learn unlabeled directed graphs. In: 35th IEEE Annual Symposium on Foundations of Computer Science, FOCS 1994, pp. 75\u201385. IEEE Computer Society (1994). \n                    https:\/\/doi.org\/10.1109\/SFCS.1994.365703","DOI":"10.1109\/SFCS.1994.365703"},{"key":"447_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., Carufel, J.D., Durocher, S.: Searching on a line: a complete characterization of the optimal solution. Theor. Comput. Sci. 569, 24\u201342 (2015). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2014.12.007","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"447_CR12","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/992287.992304","volume":"35","author":"M Chrobak","year":"2004","unstructured":"Chrobak, M.: A princess swimming in the fog looking for a monster cow. SIGACT News 35(2), 74\u201378 (2004). \n                    https:\/\/doi.org\/10.1145\/992287.992304","journal-title":"SIGACT News"},{"key":"447_CR13","doi-asserted-by":"publisher","unstructured":"Chrobak, M., G\u0105sieniec, L., Gorry, T., Martin, R.: Group search on the line. In: Italiano, G.F., Margaria-Steffen, T., Pokorn\u00fd, J., Quisquater, J., Wattenhofer, R. (eds.) Current Trends in Theory and Practice of Computer Science, SOFSEM 2015, LNCS, vol. 8939, pp. 164\u2013176. Springer (2015). \n                    https:\/\/doi.org\/10.1007\/978-3-662-46078-8_14","DOI":"10.1007\/978-3-662-46078-8_14"},{"key":"447_CR14","doi-asserted-by":"publisher","unstructured":"Czyzowicz, J., Dobrev, S., Georgiou, K., Kranakis, E., MacQuarrie, F.: Evacuating two robots from multiple unknown exits in a circle. In: Proc.\u00a017th International Conference on Distributed Computing and Networking, ICDCN 2016, pp. 28:1\u201328:8. ACM (2016). \n                    https:\/\/doi.org\/10.1145\/2833312.2833318","DOI":"10.1145\/2833312.2833318"},{"key":"447_CR15","doi-asserted-by":"publisher","unstructured":"Czyzowicz, J., Georgiou, K., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S.M.: Search on a line by byzantine robots. In: Proc.\u00a027th International Symposium on Algorithms and Computation, ISAAC 2016, pp. 27:1\u201327:12 (2016). \n                    https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2016.27","DOI":"10.4230\/LIPIcs.ISAAC.2016.27"},{"key":"447_CR16","doi-asserted-by":"publisher","unstructured":"Czyzowicz, J., Georgiou, K., Kranakis, E., MacQuarrie, F., Pajak, D.: Fence patrolling with two-speed robots. In: Proc.\u00a05th the International Conference on Operations Research and Enterprise Systems, ICORES 2016, pp. 229\u2013241. SciTePress (2016). \n                    https:\/\/doi.org\/10.5220\/0005687102290241","DOI":"10.5220\/0005687102290241"},{"key":"447_CR17","doi-asserted-by":"publisher","unstructured":"Czyzowicz, J., Georgiou, K., Kranakis, E., Narayanan, L., Opatrny, J., Vogtenhuber, B.: Evacuating robots from a disk using face-to-face communication (extended abstract). In: Proc.\u00a09th International Conference on Algorithms and Complexity, CIAC 2015, LNCS, vol. 9079, pp. 140\u2013152. Springer (2015). \n                    https:\/\/doi.org\/10.1007\/978-3-319-18173-8_10","DOI":"10.1007\/978-3-319-18173-8_10"},{"key":"447_CR18","doi-asserted-by":"publisher","unstructured":"Czyzowicz, J., G\u0105sieniec, L., Gorry, T., Kranakis, E., Martin, R., Paj\u0105k, D.: Evacuating robots via unknown exit in a disk. In: Kuhn, F. (ed.) Distributed Computing, DISC 2014, LNCS, vol. 8784, pp. 122\u2013136. Springer (2014). \n                    https:\/\/doi.org\/10.1007\/978-3-662-45174-8_9","DOI":"10.1007\/978-3-662-45174-8_9"},{"key":"447_CR19","doi-asserted-by":"publisher","unstructured":"Czyzowicz, J., G\u0105sieniec, L., Kosowski, A., Kranakis, E.: Boundary patrolling by mobile agents with distinct maximal speeds. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) Algorithms, ESA 2011, LNCS, vol. 6942, pp. 701\u2013712. Springer (2011). \n                    https:\/\/doi.org\/10.1007\/978-3-642-23719-5_59","DOI":"10.1007\/978-3-642-23719-5_59"},{"key":"447_CR20","doi-asserted-by":"publisher","unstructured":"Czyzowicz, J., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J.: Search on a line with faulty robots. In: Proc.\u00a0ACM Symposium on Principles of Distributed Computing, PODC 2016, pp. 405\u2013414. ACM (2016). \n                    https:\/\/doi.org\/10.1145\/2933057.2933102","DOI":"10.1145\/2933057.2933102"},{"key":"447_CR21","doi-asserted-by":"publisher","unstructured":"Czyzowicz, J., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S.M.: Wireless autonomous robot evacuation from equilateral triangles and squares. In: Proc.\u00a014th International Conference on Ad-hoc, Mobile, and Wireless Networks, ADHOC-NOW 2015, LNCS, vol. 9143, pp. 181\u2013194. Springer (2015). \n                    https:\/\/doi.org\/10.1007\/978-3-319-19662-6_13","DOI":"10.1007\/978-3-319-19662-6_13"},{"issue":"2\u20133","key":"447_CR22","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\u20133), 342\u2013355 (2006). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2006.05.018","journal-title":"Theor. Comput. Sci."},{"key":"447_CR23","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.ic.2014.12.005","volume":"243","author":"D Dereniowski","year":"2015","unstructured":"Dereniowski, D., Disser, Y., Kosowski, A., Paj\u0105k, D., Uzna\u0144ski, P.: Fast collaborative graph exploration. Inf. Comput. 243, 37\u201349 (2015). \n                    https:\/\/doi.org\/10.1016\/j.ic.2014.12.005","journal-title":"Inf. Comput."},{"issue":"2","key":"447_CR24","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1137\/S0097539794279201","volume":"27","author":"G Dudek","year":"1998","unstructured":"Dudek, G., Romanik, K., Whitesides, S.: Localizing a robot with minimum travel. SIAM J. Comput. 27(2), 583\u2013604 (1998). \n                    https:\/\/doi.org\/10.1137\/S0097539794279201","journal-title":"SIAM J. Comput."},{"key":"447_CR25","doi-asserted-by":"publisher","unstructured":"Feinerman, O., Korman, A., Lotker, Z., Sereni, J.: Collaborative search on the plane without communication. In: Kowalski, D., Panconesi, A. (eds.) ACM Symposium on Principles of Distributed Computing, PODC 2012, pp. 77\u201386. ACM (2012). \n                    https:\/\/doi.org\/10.1145\/2332432.2332444","DOI":"10.1145\/2332432.2332444"},{"issue":"3","key":"447_CR26","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/j.tcs.2008.02.040","volume":"399","author":"FV Fomin","year":"2008","unstructured":"Fomin, F.V., Thilikos, D.M.: An annotated bibliography on guaranteed graph searching. Theor. Comput. Sci. 399(3), 236\u2013245 (2008). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2008.02.040","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"447_CR27","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/net.20127","volume":"48","author":"P Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., G\u0105sieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks 48(3), 166\u2013177 (2006). \n                    https:\/\/doi.org\/10.1002\/net.20127","journal-title":"Networks"},{"issue":"4","key":"447_CR28","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s001820000056","volume":"29","author":"S Gal","year":"2001","unstructured":"Gal, S.: On the optimality of a simple strategy for searching graphs. Int. J. Game Theory 29(4), 533\u2013542 (2001). \n                    https:\/\/doi.org\/10.1007\/s001820000056","journal-title":"Int. J. Game Theory"},{"issue":"4","key":"447_CR29","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.cosrev.2010.05.001","volume":"4","author":"SK Ghosh","year":"2010","unstructured":"Ghosh, S.K., Klein, R.: Online algorithms for searching and exploration in the plane. Comput. Sci. Rev. 4(4), 189\u2013201 (2010). \n                    https:\/\/doi.org\/10.1016\/j.cosrev.2010.05.001","journal-title":"Comput. Sci. Rev."},{"issue":"4","key":"447_CR30","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1287\/opre.49.4.501.11227","volume":"49","author":"P Jaillet","year":"2001","unstructured":"Jaillet, P., Stafford, M.: Online searching. Oper. Res. 49(4), 501\u2013515 (2001). \n                    https:\/\/doi.org\/10.1287\/opre.49.4.501.11227","journal-title":"Oper. Res."},{"issue":"11","key":"447_CR31","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1016\/j.ipl.2009.01.020","volume":"109","author":"A Jez","year":"2009","unstructured":"Jez, A., Lopuszanski, J.: On the two-dimensional cow search problem. Inf. Process. Lett. 109(11), 543\u2013547 (2009). \n                    https:\/\/doi.org\/10.1016\/j.ipl.2009.01.020","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"447_CR32","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/inco.1996.0092","volume":"131","author":"M Kao","year":"1996","unstructured":"Kao, M., 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). \n                    https:\/\/doi.org\/10.1006\/inco.1996.0092","journal-title":"Inf. Comput."},{"issue":"2","key":"447_CR33","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s00446-014-0226-3","volume":"28","author":"A Kawamura","year":"2015","unstructured":"Kawamura, A., Kobayashi, Y.: Fence patrolling by mobile agents with distinct speeds. Distrib. Comput. 28(2), 147\u2013154 (2015). \n                    https:\/\/doi.org\/10.1007\/s00446-014-0226-3","journal-title":"Distrib. Comput."},{"key":"447_CR34","doi-asserted-by":"publisher","unstructured":"Langetepe, E.: On the optimality of spiral search. In: Proc.\u00a0Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 1\u201312 (2010). \n                    https:\/\/doi.org\/10.1137\/1.9781611973075.1","DOI":"10.1137\/1.9781611973075.1"},{"key":"447_CR35","doi-asserted-by":"publisher","DOI":"10.1515\/9781400842063","volume-title":"Chases and Escapes: The Mathematics of Pursuit and Evasion","author":"PJ Nahin","year":"2012","unstructured":"Nahin, P.J.: Chases and Escapes: The Mathematics of Pursuit and Evasion. Princeton University Press, Princeton (2012)"},{"issue":"3","key":"447_CR36","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1002\/net.21453","volume":"59","author":"A Pelc","year":"2012","unstructured":"Pelc, A.: Deterministic rendezvous in networks: a comprehensive survey. Networks 59(3), 331\u2013347 (2012). \n                    https:\/\/doi.org\/10.1002\/net.21453","journal-title":"Networks"},{"issue":"3","key":"447_CR37","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF01298332","volume":"71","author":"JM Wills","year":"1967","unstructured":"Wills, J.M.: Zwei S\u00e4tze \u00fcber inhomogene diophantische approximation von Irrationalzahlen. Monatsh. Math. 71(3), 263\u2013269 (1967). \n                    https:\/\/doi.org\/10.1007\/BF01298332","journal-title":"Monatsh. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0447-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0447-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0447-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T11:39:13Z","timestamp":1569065953000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0447-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,7]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["447"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0447-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,7]]},"assertion":[{"value":"16 January 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 April 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}