{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,18]],"date-time":"2024-07-18T02:53:07Z","timestamp":1721271187394},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,9,7]],"date-time":"2011-09-07T00:00:00Z","timestamp":1315353600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,5]]},"DOI":"10.1007\/s00224-011-9360-5","type":"journal-article","created":{"date-parts":[[2011,9,6]],"date-time":"2011-09-06T18:24:40Z","timestamp":1315333480000},"page":"611-620","source":"Crossref","is-referenced-by-count":8,"title":["Cops and Robber Game Without Recharging"],"prefix":"10.1007","volume":"50","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,9,7]]},"reference":[{"key":"9360_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(84)90073-8","volume":"8","author":"M. Aigner","year":"1984","unstructured":"Aigner, M., Fromme, M.: A game of cops and robbers. Discrete Appl. Math. 8, 1\u201311 (1984)","journal-title":"Discrete Appl. Math."},{"key":"9360_CR2","first-page":"5","volume":"59","author":"B. Alspach","year":"2006","unstructured":"Alspach, B.: Searching and sweeping graphs: a brief survey. Matematiche (Catania) 59, 5\u201337 (2006)","journal-title":"Matematiche (Catania)"},{"key":"9360_CR3","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1145\/1247069.1247085","volume-title":"Proceedings of the 23d Annual Symposium on Computational Geometry (SCG 07)","author":"A. Dumitrescu","year":"2007","unstructured":"Dumitrescu, A., Suzuki, I., Zylinski, P.: Offline variants of the \u201clion and man\u201d problem. In: Proceedings of the 23d Annual Symposium on Computational Geometry (SCG 07), New York, NY, USA, pp.\u00a0102\u2013111. ACM, New York (2007)"},{"key":"9360_CR4","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/j.tcs.2008.02.040","volume":"399","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Thilikos, D.M.: An annotated bibliography on guaranteed graph searching. Theor. Comput. Sci. 399, 236\u2013245 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"9360_CR5","doi-asserted-by":"crossref","first-page":"1167","DOI":"10.1016\/j.tcs.2009.12.010","volume":"411","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Golovach, P.A., Kratochv\u00edl, J., Nisse, N., Suchan, K.: Pursuing a fast robber on a graph. Theor. Comput. Sci. 411, 1167\u20131181 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"9360_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/978-3-642-13731-0_26","volume-title":"Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010)","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D.: Cops and robber game without recharging. In: Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010). Lecture Notes in Computer Science, vol. 6139, pp. 273\u2013284. Springer, Berlin (2010)"},{"key":"9360_CR7","volume-title":"A guide to the theory of NP-completeness. A Series of Books in the Mathematical Sciences","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. In: A guide to the theory of NP-completeness. A Series of Books in the Mathematical Sciences. Freeman, San Francisco (1979)"},{"key":"9360_CR8","first-page":"1536","volume-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI 03)","author":"M. Goldenberg","year":"2003","unstructured":"Goldenberg, M., Kovarsky, A., Wu, X., Schaeffer, J.: Multiple agents moving target search. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI 03), San Francisco, CA, USA, pp. 1536\u20131538. Morgan Kaufmann, San Mateo (2003)"},{"key":"9360_CR9","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0304-3975(95)80026-6","volume":"143","author":"A.S. Goldstein","year":"1995","unstructured":"Goldstein, A.S., Reingold, E.M.: The complexity of pursuit on a graph. Theor. Comput. Sci. 143, 93\u2013112 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"9360_CR10","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1142\/S0218195999000273","volume":"9","author":"L.J. Guibas","year":"1996","unstructured":"Guibas, L.J., Latombe, J.C., Lavalle, S.M., Lin, D., Motwani, R.: A visibility-based pursuit-evasion problem. Int. J. Comput. Geom. Appl. 9, 471\u2013494 (1996)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9360_CR11","volume-title":"Differential Games. A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization","author":"R. Isaacs","year":"1965","unstructured":"Isaacs, R.: Differential Games. A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. Wiley, New York (1965)"},{"key":"9360_CR12","first-page":"204","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)","author":"T. Ishida","year":"1991","unstructured":"Ishida, T., Korf, R.E.: Moving target search. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), vol. 91, pp. 204\u2013211 (1991)"},{"key":"9360_CR13","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1109\/34.387507","volume":"17","author":"T. Ishida","year":"1995","unstructured":"Ishida, T., Korf, R.E.: Moving-target search: A real-time search for changing goals. IEEE Trans. Pattern Anal. Mach. Intell. 17, 609\u2013619 (1995)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"9360_CR14","volume-title":"Littlewood\u2019s Miscellany","author":"J.E. Littlewood","year":"1986","unstructured":"Littlewood, J.E.: Littlewood\u2019s Miscellany. Cambridge University Press, Cambridge (1986). Edited and with a foreword by B\u00e9la Bollob\u00e1s"},{"key":"9360_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1541895.1541907","volume":"7","author":"P.K.K. Loh","year":"2009","unstructured":"Loh, P.K.K., Prakash, E.C.: Novel moving target search algorithms for computer gaming. Comput. Entertain. 7, 1\u201316 (2009)","journal-title":"Comput. Entertain."},{"key":"9360_CR16","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/42267.42268","volume":"35","author":"N. Megiddo","year":"1988","unstructured":"Megiddo, N., Hakimi, S.L., Garey, M.R., Johnson, D.S., Papadimitriou, C.H.: The complexity of searching a graph. J. Assoc. Comput. Mach. 35, 18\u201344 (1988)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9360_CR17","first-page":"584","volume-title":"Proceedings of the 21st International Joint Conference on Artificial Intelligence","author":"C. Moldenhauer","year":"2009","unstructured":"Moldenhauer, C., Sturtevant, N.R.: Evaluating strategies for running from the cops. In: Proceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI, pp. 584\u2013589 (2009)"},{"key":"9360_CR18","first-page":"1249","volume-title":"Proceedings of the 8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009)","author":"C. Moldenhauer","year":"2009","unstructured":"Moldenhauer, C., Sturtevant, N.R.: Optimal solutions for moving target search. In: Proceedings of the 8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), IFAAMAS, pp. 1249\u20131250 (2009)"},{"key":"9360_CR19","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0012-365X(83)90160-7","volume":"43","author":"R. Nowakowski","year":"1983","unstructured":"Nowakowski, R., Winkler, P.: Vertex-to-vertex pursuit in a graph. Discrete Math. 43, 235\u2013239 (1983)","journal-title":"Discrete Math."},{"key":"9360_CR20","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0195-6698(86)80017-8","volume":"7","author":"A. Quilliot","year":"1986","unstructured":"Quilliot, A.: Some results about pursuit games on metric spaces obtained through graph theory techniques. Eur. J. Comb. 7, 55\u201366 (1986)","journal-title":"Eur. J. Comb."},{"key":"9360_CR21","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1016\/S0304-3975(00)00411-4","volume":"259","author":"J. Sgall","year":"2001","unstructured":"Sgall, J.: Solution of David Gale\u2019s lion and man problem. Theor. Comput. Sci. 259, 663\u2013670 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"9360_CR22","doi-asserted-by":"crossref","first-page":"1024","DOI":"10.1137\/0219070","volume":"19","author":"K. Sugihara","year":"1990","unstructured":"Sugihara, K., Suzuki, I., Yamashita, M.: The searchlight scheduling problem. SIAM J. Comput. 19, 1024\u20131040 (1990)","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9360-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9360-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9360-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:23Z","timestamp":1558698863000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9360-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,7]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,5]]}},"alternative-id":["9360"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9360-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9,7]]}}}