{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T12:16:13Z","timestamp":1782476173106,"version":"3.54.5"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,8,31]],"date-time":"2018-08-31T00:00:00Z","timestamp":1535673600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"ANR Stint","award":["ANR-13-BS02-0007"],"award-info":[{"award-number":["ANR-13-BS02-0007"]}]},{"name":"ANR \u201cInvestments for the Future\u201d","award":["ANR-11- LABX-0031-01"],"award-info":[{"award-number":["ANR-11- LABX-0031-01"]}]},{"name":"Inria team AlDyNet"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s00453-018-0503-9","type":"journal-article","created":{"date-parts":[[2018,8,31]],"date-time":"2018-08-31T09:43:29Z","timestamp":1535708609000},"page":"212-244","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Study of a Combinatorial Game in Graphs Through Linear Programming"],"prefix":"10.1007","volume":"82","author":[{"given":"Nathann","family":"Cohen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fionn","family":"Mc Inerney","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4500-5078","authenticated-orcid":false,"given":"Nicolas","family":"Nisse","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"St\u00e9phane","family":"P\u00e9rennes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,8,31]]},"reference":[{"key":"503_CR1","doi-asserted-by":"publisher","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\u201312 (1984)","journal-title":"Discrete Appl. Math."},{"key":"503_CR2","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/j.jcta.2017.06.009","volume":"152","author":"P Balister","year":"2017","unstructured":"Balister, P., Shaw, A., Bollob\u00e1s, B., Narayanan, B.P.: Catching a fast robber on the grid. JCTA 152, 341\u2013352 (2017)","journal-title":"JCTA"},{"key":"503_CR3","first-page":"33","volume":"85","author":"I Beaton","year":"2013","unstructured":"Beaton, I., Finbow, S., MacDonald, J.A.: Eternal domination numbers of \n$$4\\times n$$\n\n\n\n\n4\n\u00d7\nn\n\n\n\n\n grid graphs. J. Comb. Math. Comb. Comput. 85, 33\u201348 (2013)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"43","key":"503_CR4","doi-asserted-by":"publisher","first-page":"3834","DOI":"10.1016\/j.tcs.2010.07.003","volume":"411","author":"A Bonato","year":"2010","unstructured":"Bonato, A., Chiniforooshan, E., Pralat, P.: Cops and robbers from a distance. Theor. Comput. Sci. 411(43), 3834\u20133844 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"503_CR5","doi-asserted-by":"publisher","DOI":"10.1090\/stml\/061","volume-title":"The Game of Cops and Robbers on Graphs","author":"A Bonato","year":"2011","unstructured":"Bonato, A., Nowakowski, R.J.: The Game of Cops and Robbers on Graphs. American Mathematical Society, Providence (2011)"},{"key":"503_CR6","volume-title":"Graph Theory, Graduate Texts in Mathematics","author":"JA Bondy","year":"2008","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory, Graduate Texts in Mathematics, vol. 244. Springer, Berlin (2008)"},{"key":"503_CR7","first-page":"179","volume":"50","author":"A Burger","year":"2004","unstructured":"Burger, A., Cockayne, E.J., Gr\u00fcndlingh, W.R., Mynhardt, C.M., van Vuuren, J.H., Winterbach, W.: Infinite order domination in graphs. J. Comb. Math. Comb. Comput. 50, 179\u2013194 (2004)","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"503_CR8","unstructured":"Cohen, N., Hilaire, M., Martins, N.A., Nisse, N., P\u00e9rennes, S.: Spy-game on graphs. In: 8th International Conference on Fun with Algorithms, FUN 2016, pp. 10:1\u201310:16 (2016)"},{"key":"503_CR9","unstructured":"Cohen, N., Mc Inerney, F., Nisse, N., P\u00e9rennes, S.: Study of a combinatorial game in graphs through linear programming. In: 28th International Symposium on Algorithms and Computation (ISAAC 2017), LIPIcs 92, Schloss Dagstuhl, pp. 22:1\u201322:13 (2017). \nhttps:\/\/hal.archives-ouvertes.fr\/hal-01462890"},{"key":"503_CR10","unstructured":"Cohen, N., Martins, N.A., Mc Inerney, F., Nisse, N., P\u00e9rennes, S., Sampaio, R.: Spy-game on graphs: complexity and simple topologies. Theor. Comput. Sci. 725, 1\u201315 (2018). \nhttps:\/\/hal.archives-ouvertes.fr\/hal-01782246v1"},{"key":"503_CR11","unstructured":"Delaney, A.Z., Messinger, M.E.: Closing the gap: Eternal domination on \n$$3\\times n$$\n\n\n\n\n3\n\u00d7\nn\n\n\n\n\n grids. Contrib. Discrete Math. (2015)"},{"key":"503_CR12","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Giroire, F., Jean-Marie, A., Mazauric, D., Nisse, N.: To satisfy impatient web surfers is hard. In: 6th International Conference on Fun with Algorithms (FUN), LNCS, vol. 7288, pp. 166\u2013176 (2012)","DOI":"10.1007\/978-3-642-30347-0_18"},{"issue":"7\u20139","key":"503_CR13","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1016\/j.tcs.2009.12.010","volume":"411","author":"FV 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(7\u20139), 1167\u20131181 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"503_CR14","volume-title":"20th International Colloquium on Structural Information and Communication Complexity (SIROCCO). Lecture Notes in Computer Science","author":"F Giroire","year":"2013","unstructured":"Giroire, F., Mazauric, D., Nisse, N., P\u00e9rennes, S., Soares, R.P.: Connected surveillance game. In: Moscibroda, T., Rescigno, A.A. (eds.) 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO). Lecture Notes in Computer Science. Springer, Berlin (2013)"},{"key":"503_CR15","unstructured":"Giroire, F., Nisse, N., P\u00e9rennes, S., Soares, R.P.: Fractional combinatorial games. Technical report, INRIA, (2013). RR8371. \nhttp:\/\/hal.inria.fr\/hal-00865345"},{"key":"503_CR16","first-page":"160","volume":"52","author":"W Goddard","year":"2005","unstructured":"Goddard, W., Hedetniemi, S.M., Hedetniemi, S.T.: Eternal security in graphs. J. Comb. Math. Comb. Comput. 52, 160\u2013180 (2005)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"3","key":"503_CR17","doi-asserted-by":"publisher","first-page":"1443","DOI":"10.1137\/11082574","volume":"25","author":"D Gon\u00e7alves","year":"2011","unstructured":"Gon\u00e7alves, D., Pinlou, A., Rao, M., Thomass\u00e9, S.: The domination number of grids. SIAM J. Discrete Math. 25(3), 1443\u20131453 (2011)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"503_CR18","first-page":"40","volume":"5","author":"G Joret","year":"2010","unstructured":"Joret, G., Kaminski, M., Theis, D.O.: The cops and robber game on graphs with forbidden (induced) subgraphs. Contrib. Discrete Math. 5(2), 40\u201351 (2010)","journal-title":"Contrib. Discrete Math."},{"key":"503_CR19","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/j.jctb.2014.11.002","volume":"111","author":"WB Kinnersley","year":"2015","unstructured":"Kinnersley, W.B.: Cops and robbers is exptime-complete. JCTB 111, 201\u2013220 (2015)","journal-title":"JCTB"},{"key":"503_CR20","first-page":"97","volume":"68","author":"WF Klostermeyer","year":"2009","unstructured":"Klostermeyer, W.F., MacGillivray, G.: Eternal dominating sets in graphs. J. Comb. Math. Comb. Comput. 68, 97\u2013111 (2009)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"3","key":"503_CR21","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1007\/s00453-014-9871-y","volume":"72","author":"A Kosowski","year":"2015","unstructured":"Kosowski, A., Li, B., Nisse, N., Suchan, K.: k-Chordal graphs: from cops and robber to compact routing via treewidth. Algorithmica 72(3), 758\u2013777 (2015)","journal-title":"Algorithmica"},{"key":"503_CR22","doi-asserted-by":"crossref","unstructured":"Kusters, R.: Memoryless determinacy of parity games. In: Automata, Logics, and Infinite Games: A Guide to Current Research, LNCS, vol. 2500, pp. 95\u2013106 (2002)","DOI":"10.1007\/3-540-36387-4_6"},{"key":"503_CR23","doi-asserted-by":"crossref","unstructured":"Lamprou, I., Martin, R., Schewe, S.: Perpetually dominating large grids. In: 10th International Conference on Algorithms and Complexity (CIAC 2017), LNCS, vol. 10236, pp. 393\u2013404 (2017)","DOI":"10.1007\/978-3-319-57586-5_33"},{"key":"503_CR24","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0012-365X(83)90160-7","volume":"43","author":"RJ Nowakowski","year":"1983","unstructured":"Nowakowski, R.J., Winkler, P.: Vertex-to-vertex pursuit in a graph. Discrete Math. 43, 235\u2013239 (1983)","journal-title":"Discrete Math."},{"key":"503_CR25","unstructured":"Quilliot, A.: Probl\u00e8mes de jeux, de point fixe, de connectivit\u00e9 et de repr\u00e9sentation sur des graphes, des ensembles ordonn\u00e9s et des hypergraphes. Doctorat d\u2019\u00e9tat, Univ. Paris 4 (1983)"},{"key":"503_CR26","first-page":"243","volume-title":"Categorical Perspectives (Kent, OH, 1998). Trends in Mathematics","author":"BSW Schr\u00f6der","year":"2001","unstructured":"Schr\u00f6der, B.S.W.: The copnumber of a graph is bounded by \n$$\\lfloor \\frac{3}{2} genus (g) \\rfloor + 3$$\n\n\n\n\n\u230a\n\n3\n2\n\ng\ne\nn\nu\ns\n\n(\ng\n)\n\n\u230b\n+\n3\n\n\n\n\n. In: Koslowski, J., Melton, A. (eds.) Categorical Perspectives (Kent, OH, 1998). Trends in Mathematics, pp. 243\u2013263. Birkh\u00e4user, Boston (2001)"},{"issue":"3","key":"503_CR27","doi-asserted-by":"publisher","first-page":"1438","DOI":"10.1137\/100812963","volume":"25","author":"A Scott","year":"2011","unstructured":"Scott, A., Sudakov, B.: A bound for the cops and robbers problem. SIAM J. Discrete Math. 25(3), 1438\u20131442 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"503_CR28","first-page":"83","volume":"97","author":"CM Bommel van","year":"2016","unstructured":"van Bommel, C.M., van Bommel, M.F.: Eternal domination numbers of \n$$5\\times n$$\n\n\n\n\n5\n\u00d7\nn\n\n\n\n\n grid graphs. J. Comb. Math. Comb. Comput. 97, 83\u2013102 (2016)","journal-title":"J. Comb. Math. Comb. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0503-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0503-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0503-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,27]],"date-time":"2020-01-27T20:05:38Z","timestamp":1580155538000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0503-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,31]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["503"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0503-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,31]]},"assertion":[{"value":"18 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}