{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:39Z","timestamp":1759638879614,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662489703"},{"type":"electronic","value":"9783662489710"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48971-0_30","type":"book-chapter","created":{"date-parts":[[2015,11,26]],"date-time":"2015-11-26T04:00:57Z","timestamp":1448510457000},"page":"343-354","source":"Crossref","is-referenced-by-count":10,"title":["When Patrolmen Become Corrupted: Monitoring a Graph Using Faulty Mobile Robots"],"prefix":"10.1007","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":[[2015,11,27]]},"reference":[{"key":"30_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":"30_CR2","doi-asserted-by":"publisher","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":"30_CR3","volume-title":"Optimizing Randomized Patrols","author":"S Alpern","year":"2009","unstructured":"Alpern, S., Morton, A., Papadaki, K.: Optimizing Randomized Patrols. Operational Research Group, London School of Economics and Political Science (2009)"},{"issue":"5","key":"30_CR4","doi-asserted-by":"publisher","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":"30_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":"30_CR6","doi-asserted-by":"crossref","unstructured":"Chevaleyre, Y.: Theoretical analysis of the multi-agent patrolling problem. In: IAT, pages 302\u2013308 (2004)","DOI":"10.1109\/IAT.2004.1342959"},{"issue":"1","key":"30_CR7","doi-asserted-by":"publisher","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":"30_CR8","doi-asserted-by":"publisher","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":"30_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1007\/978-3-642-23719-5_59","volume-title":"Algorithms \u2013 ESA 2011","author":"J Czyzowicz","year":"2011","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.) ESA 2011. LNCS, vol. 6942, pp. 701\u2013712. Springer, Heidelberg (2011)"},{"key":"30_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/11864219_4","volume-title":"Distributed Computing","author":"X D\u00e9fago","year":"2006","unstructured":"D\u00e9fago, X., Gradinariu, M., Messika, S., Raipin-Parv\u00e9dy, P.: Fault-tolerant and self-stabilizing mobile robots gathering. In: Dolev, S. (ed.) DISC 2006. LNCS, vol. 4167, pp. 46\u201360. Springer, Heidelberg (2006)"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Dieudonn\u00e9, Y., Pelc, A., Peleg, D.: Gathering despite mischief. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 527\u2013540. SIAM (2012)","DOI":"10.1137\/1.9781611973099.45"},{"issue":"3","key":"30_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":"30_CR13","doi-asserted-by":"publisher","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":"30_CR14","first-page":"63","volume":"1","author":"Y Elmaliach","year":"2008","unstructured":"Elmaliach, Y., Shiloni, A., Kaminka, G.A.: A realistic model of frequency-based multi-robot polyline patrolling. AAMAS 1, 63\u201370 (2008)","journal-title":"AAMAS"},{"key":"30_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-642-15461-4_11","volume-title":"Swarm Intelligence","author":"Y Elor","year":"2010","unstructured":"Elor, Y., Bruckstein, A.M.: Autonomous multi-agent cycle based patrolling. In: Dorigo, M., Birattari, M., Di Caro, G.A., Doursat, R., Engelbrecht, A.P., Floreano, D., Gambardella, L.M., Gro\u00df, R., \u015eahin, E., Sayama, H., St\u00fctzle, T. (eds.) ANTS 2010. LNCS, vol. 6234, pp. 119\u2013130. Springer, Heidelberg (2010)"},{"key":"30_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":"30_CR17","doi-asserted-by":"publisher","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":"30_CR18","doi-asserted-by":"publisher","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":"30_CR19","doi-asserted-by":"publisher","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."},{"key":"30_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1007\/978-3-642-35261-4_62","volume-title":"Algorithms and Computation","author":"A Kawamura","year":"2012","unstructured":"Kawamura, A., Kobayashi, Y.: Fence patrolling by mobile agents with distinct speeds. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 598\u2013608. Springer, Heidelberg (2012)"},{"key":"30_CR21","unstructured":"Kotzig, A.: Hamilton graphs and hamilton circuits. In: Theory of Graphs and its Applications, Proceedings of the Symposium of Smolenice, pp. 63\u201382. Publ. House Czechoslovak Acad. Sci. (1964)"},{"key":"30_CR22","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/3-540-36483-8_11","volume-title":"Multi-Agent-Based Simulation II","author":"A Machado","year":"2003","unstructured":"Machado, A., Ramalho, G.L., Zucker, J.-D., Drogoul, A.: Multi-agent patrolling: an empirical analysis of alternative architectures. In: Sichman, J.S., Bousquet, F., Davidsson, P. (eds.) MABS 2002. LNCS (LNAI), vol. 2581, pp. 155\u2013170. Springer, Heidelberg (2003)"},{"key":"30_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: Robotics and Biomimetics (ROBIO), pp. 735\u2013740 (2009)","DOI":"10.1109\/ROBIO.2009.5420581"},{"key":"30_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":"30_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/3-540-46784-X_24","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J-H Park","year":"1999","unstructured":"Park, J.-H., Kim, H.-C.: Dihamiltonian decomposition of regular graphs with degree three. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol. 1665, pp. 240\u2013249. Springer, Heidelberg (1999)"},{"key":"30_CR26","doi-asserted-by":"crossref","unstructured":"Pasqualetti, F., Franchi, A., Bullo, F.: On optimal cooperative patrolling. In: CDC, pp. 7153\u20137158 (2010)","DOI":"10.1109\/CDC.2010.5717873"},{"key":"30_CR27","series-title":"IFIP Advances in Information and Communication Technology","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-3-642-19170-1_15","volume-title":"Technological Innovation for Sustainability","author":"D Portugal","year":"2011","unstructured":"Portugal, D., Rocha, R.: A survey on multi-robot patrolling algorithms. In: Camarinha-Matos, L.M. (ed.) Technological Innovation for Sustainability. IFIP AICT, vol. 349, pp. 139\u2013146. Springer, Heidelberg (2011)"},{"key":"30_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/11945529_24","volume-title":"Principles of Distributed Systems","author":"S Souissi","year":"2006","unstructured":"Souissi, S., D\u00e9fago, X., Yamashita, M.: Gathering asynchronous mobile robots with inaccurate compasses. In: Shvartsman, M.M.A.A. (ed.) OPODIS 2006. LNCS, vol. 4305, pp. 333\u2013349. Springer, Heidelberg (2006)"},{"issue":"1","key":"30_CR29","doi-asserted-by":"publisher","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":"30_CR30","doi-asserted-by":"publisher","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":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48971-0_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T15:12:03Z","timestamp":1748704323000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48971-0_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662489703","9783662489710"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48971-0_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}