{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T11:20:31Z","timestamp":1778671231131,"version":"3.51.4"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,10,18]],"date-time":"2016-10-18T00:00:00Z","timestamp":1476748800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"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\/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\/501100004489","name":"Mitacs","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004489","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00453-016-0233-9","type":"journal-article","created":{"date-parts":[[2016,10,18]],"date-time":"2016-10-18T13:22:30Z","timestamp":1476796950000},"page":"925-940","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["When Patrolmen Become Corrupted: Monitoring a Graph Using Faulty Mobile Robots"],"prefix":"10.1007","volume":"79","author":[{"given":"Jurek","family":"Czyzowicz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leszek","family":"Gasieniec","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adrian","family":"Kosowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evangelos","family":"Kranakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Krizanc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Najmeh","family":"Taleb","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,10,18]]},"reference":[{"key":"233_CR1","doi-asserted-by":"crossref","unstructured":"Agmon, N., Kraus, S., Kaminka, G.A.: Multi-robot perimeter patrol in adversarial settings. In: ICRA, pp. 2339\u20132345 (2008)","DOI":"10.1109\/ROBOT.2008.4543563"},{"issue":"1","key":"233_CR2","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1137\/050645221","volume":"36","author":"N Agmon","year":"2006","unstructured":"Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36(1), 56\u201382 (2006)","journal-title":"SIAM J. Comput."},{"key":"233_CR3","unstructured":"Alpern, S., Morton, A., Papadaki, K.: Optimizing Randomized Patrols. Operational Research Group, London School of Economics and Political Science, Working Paper LSEOR 09.116 (2009)"},{"issue":"5","key":"233_CR4","doi-asserted-by":"crossref","first-page":"1246","DOI":"10.1287\/opre.1110.0983","volume":"59","author":"S Alpern","year":"2011","unstructured":"Alpern, S., Morton, A., Papadaki, K.: Patrolling games. Oper. Res. 59(5), 1246\u20131257 (2011)","journal-title":"Oper. Res."},{"key":"233_CR5","doi-asserted-by":"crossref","unstructured":"Amigoni, F., Basilico, N., Gatti, N., Saporiti, A., Troiani, S.: Moving game theoretical patrolling strategies from theory to practice: An USARSim simulation. In: ICRA, pp. 426\u2013431 (2010)","DOI":"10.1109\/ROBOT.2010.5509943"},{"key":"233_CR6","doi-asserted-by":"crossref","unstructured":"Chevaleyre, Y.: Theoretical analysis of the multi-agent patrolling problem. In: IAT, pp. 302\u2013308 (2004)","DOI":"10.1109\/IAT.2004.1342959"},{"issue":"1","key":"233_CR7","doi-asserted-by":"crossref","first-page":"1516","DOI":"10.1137\/S0097539704446475","volume":"41","author":"R Cohen","year":"2005","unstructured":"Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 41(1), 1516\u20131528 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"233_CR8","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1137\/060665257","volume":"38","author":"R Cohen","year":"2008","unstructured":"Cohen, R., Peleg, D.: Convergence of autonomous mobile robots with inaccurate sensors and movements. SIAM J. Comput. 38(1), 276\u2013302 (2008)","journal-title":"SIAM J. Comput."},{"key":"233_CR9","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Gasieniec, L., Kosowski, A., Kranakis, E.: Boundary patrolling by mobile agents with distinct maximal speeds. In: ESA, vol. 2011, pp. 701\u2013712 (2011)","DOI":"10.1007\/978-3-642-23719-5_59"},{"key":"233_CR10","doi-asserted-by":"crossref","unstructured":"D\u00e9fago, X., Gradinariu, M., Messika, S., Ra\u00efpin-Parv\u00e9dy, P.: Fault-tolerant and self-stabilizing mobile robots gathering. In: International Symposium on Distributed Computing, pp. 46\u201360 (2006)","DOI":"10.1007\/11864219_4"},{"issue":"1","key":"233_CR11","doi-asserted-by":"crossref","first-page":"1:1","DOI":"10.1145\/2629656","volume":"11","author":"Y Dieudonn\u00e9","year":"2014","unstructured":"Dieudonn\u00e9, Y., Pelc, A., Peleg, D.: Gathering despite mischief. ACM Trans. Algorithms 11(1), 1:1\u20131:28 (2014)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"233_CR12","doi-asserted-by":"crossref","first-page":"P3.4","DOI":"10.37236\/4063","volume":"21","author":"A Dumitrescu","year":"2014","unstructured":"Dumitrescu, A., Ghosh, A., T\u00f3th, C.D.: On fence patrolling by mobile agents. Electr. J. Comb. 21(3), P3.4 (2014)","journal-title":"Electr. J. Comb."},{"issue":"3\u20134","key":"233_CR13","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/s10472-010-9193-y","volume":"57","author":"Y Elmaliach","year":"2009","unstructured":"Elmaliach, Y., Agmon, N., Kaminka, G.A.: Multi-robot area patrol under frequency constraints. Ann. Math. Artif. Intell. 57(3\u20134), 293\u2013320 (2009)","journal-title":"Ann. Math. Artif. Intell."},{"key":"233_CR14","unstructured":"Elmaliach, Y., Shiloni, A., Kaminka, G.A.: A realistic model of frequency-based multi-robot polyline patrolling. In: AAMAS, vol. 1, pp. 63\u201370 (2008)"},{"key":"233_CR15","doi-asserted-by":"crossref","unstructured":"Elor, Y., Bruckstein, A.M.: Autonomous multi-agent cycle based patrolling. In: ANTS Conference, pp. 119\u2013130 (2010)","DOI":"10.1007\/978-3-642-15461-4_11"},{"key":"233_CR16","volume-title":"Computers and Intractability","author":"M Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability, vol. 174. Freeman, San Francisco (1979)"},{"key":"233_CR17","doi-asserted-by":"crossref","first-page":"1102","DOI":"10.1016\/j.robot.2008.01.006","volume":"56","author":"N Hazon","year":"2008","unstructured":"Hazon, N., Kaminka, G.A.: On redundancy, efficiency, and robustness in coverage for multiple robots. Robot. Auton. Syst. 56, 1102\u20131114 (2008)","journal-title":"Robot. Auton. Syst."},{"issue":"4","key":"233_CR18","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"233_CR19","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1137\/100797916","volume":"41","author":"T Izumi","year":"2012","unstructured":"Izumi, T., Souissi, S., Katayama, Y., Inuzuka, N., D\u00e9fago, X., Wada, K., Yamashita, M.: The gathering problem for two oblivious robots with unreliable compasses. SIAM J. Comput. 41(1), 26\u201346 (2012)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"233_CR20","doi-asserted-by":"crossref","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)","journal-title":"Distrib. Comput."},{"key":"233_CR21","unstructured":"Kotzig, A.: Hamilton graphs and Hamilton circuits. In Proceedings of the Symposium of Smolenice in Theory of Graphs and Its Applications, pp. 63\u201382. Publ. House Czechoslovak Acad. Sci. (1964)"},{"key":"233_CR22","doi-asserted-by":"crossref","unstructured":"Machado, A., Ramalho, G., Zucker, J.-D., Drogoul, A.: Multi-agent patrolling: an empirical analysis of alternative architectures. In: MABS, pp. 155\u2013170 (2002)","DOI":"10.1007\/3-540-36483-8_11"},{"key":"233_CR23","doi-asserted-by":"crossref","unstructured":"Marino, A., Parker, L., Antonelli, G., Caccavale, F., Chiaverini, S.: A fault-tolerant modular control approach to multi-robot perimeter patrol. In: IEEE International Conference on Robotics and Biomimetics (ROBIO), pp. 735\u2013740 (2009)","DOI":"10.1109\/ROBIO.2009.5420581"},{"key":"233_CR24","doi-asserted-by":"crossref","unstructured":"Marino, A., Parker, L.E., Antonelli, G., Caccavale, F.: Behavioral control for multi-robot perimeter patrol: a finite state automata approach. In: ICRA, pp. 831\u2013836 (2009)","DOI":"10.1109\/ROBOT.2009.5152710"},{"key":"233_CR25","doi-asserted-by":"crossref","unstructured":"Park, J., Kim, H.: Dihamiltonian decomposition of regular graphs with degree three. In: International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 240\u2013249. Springer, Berlin (1999)","DOI":"10.1007\/3-540-46784-X_24"},{"key":"233_CR26","doi-asserted-by":"crossref","unstructured":"Pasqualetti, F., Franchi, A., Bullo, F.: On optimal cooperative patrolling. In: 49th IEEE Conference on Decision and Control (CDC), pp. 7153\u20137158 (2010)","DOI":"10.1109\/CDC.2010.5717873"},{"key":"233_CR27","doi-asserted-by":"crossref","unstructured":"Portugal, D., Rocha, R.P.: A survey on multi-robot patrolling algorithms. In: Proceedings of the 2nd International Conference on Technological Innovation for Sustainability (IFIP WG 5.5), Costa de Caparica, Portugal, February 21\u201323, pp. 139\u2013146 (2011)","DOI":"10.1007\/978-3-642-19170-1_15"},{"key":"233_CR28","doi-asserted-by":"crossref","unstructured":"Souissi, S., D\u00e9fago, X., Yamashita, M.: Gathering asynchronous mobile robots with inaccurate compasses. In: International Conference on Principles of Distributed Systems, pp. 333\u2013349 (2006)","DOI":"10.1007\/11945529_24"},{"issue":"1","key":"233_CR29","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.jss.2010.08.026","volume":"84","author":"Y Yang","year":"2011","unstructured":"Yang, Y., Souissi, S., D\u00e9fago, X., Takizawa, M.: Fault-tolerant flocking for a group of autonomous mobile robots. J. Syst. Softw. 84(1), 29\u201336 (2011)","journal-title":"J. Syst. Softw."},{"issue":"3","key":"233_CR30","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s00453-003-1030-9","volume":"37","author":"V Yanovski","year":"2003","unstructured":"Yanovski, V., Wagner, I.A., Bruckstein, A.M.: A distributed ant algorithm for efficiently patrolling a network. Algorithmica 37(3), 165\u2013186 (2003)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0233-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0233-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0233-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T16:30:48Z","timestamp":1749659448000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0233-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,18]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["233"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0233-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,18]]}}}