{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:02Z","timestamp":1760202602270},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,1,6]],"date-time":"2010-01-06T00:00:00Z","timestamp":1262736000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,12]]},"DOI":"10.1007\/s00453-009-9382-4","type":"journal-article","created":{"date-parts":[[2010,1,5]],"date-time":"2010-01-05T16:44:35Z","timestamp":1262709875000},"page":"839-856","source":"Crossref","is-referenced-by-count":7,"title":["How to Guard a Graph?"],"prefix":"10.1007","volume":"61","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Hall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mat\u00fa\u0161","family":"Mihal\u00e1k","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elias","family":"Vicari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Widmayer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,1,6]]},"reference":[{"key":"9382_CR1","series-title":"A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization","volume-title":"Differential Games","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)"},{"issue":"2\u20133","key":"9382_CR2","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(2\u20133), 235\u2013239 (1983)","journal-title":"Discrete Math."},{"issue":"1","key":"9382_CR3","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), 1\u201311 (1984)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"9382_CR4","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41(5), 960\u2013981 (1994)","journal-title":"J. ACM"},{"key":"9382_CR5","volume-title":"Chases and Escapes. The Mathematics of Pursuit and Evasion","author":"P.J. Nahin","year":"2007","unstructured":"Nahin, P.J.: Chases and Escapes. The Mathematics of Pursuit and Evasion. Princeton University Press, Princeton (2007)"},{"issue":"1","key":"9382_CR6","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(1), 55\u201366 (1986)","journal-title":"Eur. J. Comb."},{"issue":"1\u20132","key":"9382_CR7","first-page":"5","volume":"59","author":"B. Alspach","year":"2006","unstructured":"Alspach, B.: Searching and sweeping graphs: a brief survey. Matematiche (Catania) 59(1\u20132), 5\u201337 (2006)","journal-title":"Matematiche (Catania)"},{"key":"9382_CR8","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."},{"issue":"1","key":"9382_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(1), 93\u2013112 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"9382_CR10","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/978-0-387-09680-3_12","volume-title":"5th IFIP International Conference on Theoretical Computer Science","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Golovach, P., Kratochv\u00edl, J.: On tractability of Cops and Robbers game. In: 5th IFIP International Conference on Theoretical Computer Science, vol. 273, pp. 171\u2013185. Springer, Berlin (2008)"},{"issue":"5","key":"9382_CR11","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1109\/TSE.1979.234213","volume":"5","author":"S.C. Ntafos","year":"1979","unstructured":"Ntafos, S.C., Hakimi, S.L.: On path cover problems in digraphs and applications to program testing. IEEE Trans. Softw. Eng. 5(5), 520\u2013529 (1979)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"9382_CR12","volume-title":"Algorithmic Combinatorics","author":"S. Even","year":"1973","unstructured":"Even, S.: Algorithmic Combinatorics. MacMillan, New York (1973)"},{"key":"9382_CR13","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999)"},{"key":"9382_CR14","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/0012-365X(72)90006-4","volume":"2","author":"L. Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz, L.: Normal hypergraphs and the perfect graph conjecture. J. Discrete Math. 2, 253\u2013267 (1972)","journal-title":"J. Discrete Math."},{"issue":"1","key":"9382_CR15","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0166-218X(02)00418-3","volume":"131","author":"E. \u010cenek","year":"2003","unstructured":"\u010cenek, E., Stewart, L.: Maximum independent set and maximum clique algorithms for overlap graphs. Discrete Appl. Math. 131(1), 77\u201391 (2003)","journal-title":"Discrete Appl. Math."},{"key":"9382_CR16","series-title":"A Series of Books in the Mathematical Sciences","volume-title":"Computers and Intractability. A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-completeness. A Series of Books in the Mathematical Sciences. Freeman, San Francisco (1979)"},{"key":"9382_CR17","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"issue":"4","key":"9382_CR18","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1006\/aama.1993.1019","volume":"14","author":"A. Berarducci","year":"1993","unstructured":"Berarducci, A., Intrigila, B.: On the cop number of a graph. Adv. Appl. Math. 14(4), 389\u2013403 (1993)","journal-title":"Adv. Appl. Math."},{"issue":"19\u201320","key":"9382_CR19","doi-asserted-by":"crossref","first-page":"2492","DOI":"10.1016\/j.disc.2005.12.038","volume":"306","author":"G. Hahn","year":"2006","unstructured":"Hahn, G., MacGillivray, G.: A note on k-cop, l-robber games on graphs. Discrete Math. 306(19\u201320), 2492\u20132497 (2006)","journal-title":"Discrete Math."},{"key":"9382_CR20","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th STOC, pp.\u00a0475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"9382_CR21","doi-asserted-by":"crossref","unstructured":"Nagamochi, H.: Cop-robber guarding game with cycle robber region. In: Proceedings of the Third International Frontiers of Algorithmics Workshop (FAW), pp.\u00a074\u201384 (2009)","DOI":"10.1007\/978-3-642-02270-8_10"},{"key":"9382_CR22","doi-asserted-by":"crossref","unstructured":"Reddy, T.V.T., Krishna, D.S., Rangan, C.P.: The guarding problem\u2014complexity and approximation. In: Proceedings of the 20th International Workshop on Combinatorial Algorithms (IWOCA), pp.\u00a0460\u2013470 (2009)","DOI":"10.1007\/978-3-642-10217-2_45"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9382-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9382-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9382-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:05Z","timestamp":1559137505000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9382-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1,6]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["9382"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9382-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1,6]]}}}