, Further connections between contract-scheduling and ray-searching problems, Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJ- CAI), pp.1516-1522, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01362953
, The theory of search games and rendez vous, 2003.
, Cops and robbers in a random graph, preprint. [BonatoN11] A. Bonato and R. Nowakowski, The Game of Cops and Robbers on Graphs, 2011.
, Lost in a Cave -Applying Graph Theory to Cave Exploration, 2011.
, An annotated bibliography on guaranteed graph searching, Theoretical Computer Science, vol.399, issue.3, pp.236-245, 2008.
DOI : 10.1016/j.tcs.2008.02.040
, The complexity of searching a graph, Journal of the ACM, vol.35, issue.1, pp.18-44, 1988.
DOI : 10.1145/42267.42268
, Pursuit-evasion in a graph, Lecture Notes in Math, vol.642, pp.426-441, 1978.
DOI : 10.1007/BFb0070400
, Graph minors ? a survey, Surveys in combinatorics, Soc. Lecture Note Ser, vol.103, pp.153-171, 1985.
, A Bound for the Cops and Robbers Problem, SIAM Journal on Discrete Mathematics, vol.25, issue.3, pp.1438-1442, 2011.
DOI : 10.1137/100812963
, Graph Searching and a Min-Max Theorem for Tree-Width, Journal of Combinatorial Theory, Series B, vol.58, issue.1, pp.22-33, 1993.
DOI : 10.1006/jctb.1993.1027
, The ???Princess and Monster??? Game on an Interval, SIAM Journal on Control and Optimization, vol.47, issue.3, pp.178-1190, 2008.
DOI : 10.1137/060672054
URL : http://www.cdam.lse.ac.uk/Reports/Files/cdam-2006-17.pdf
, A Numerical Approach to the ???Princess and Monster??? Game on an Interval, Advances in Dynamic Games and Their Applications, pp.149-157, 2009.
DOI : 10.1007/978-0-8176-4834-3_9
, Some topological questions and conjectures on Cops and Robbers It is known (see [1]) that planar graphs (graphs of genus 0) have cop number at most 3
, A game of cops and robbers, Discrete Applied Mathematics, vol.8, issue.1, pp.1-12, 1984.
DOI : 10.1016/0166-218X(84)90073-8
, Constrained Cops and Robber, 2002.
, The copnumber of a graph is bounded by 3 2 genus(G) + 3, Categorical perspectives, Trends in Mathematics, pp.243-263, 1998.
, Winning Ways for your Mathematical Plays, 1982.
, The Angel and the Devil in three dimensions, Journal of Combinatorial Theory, Series A, vol.113, issue.1, pp.176-184, 2006.
DOI : 10.1016/j.jcta.2005.03.009
, The Angel Game in the Plane, Combinatorics, Probability and Computing, vol.16, issue.03, pp.345-362, 2007.
DOI : 10.1017/S0963548306008297
, Seepage in directed acyclic graphs, Australasian Journal of Combinatorics, vol.43, pp.91-102, 2009.
, Chain-making games in grid-like posets, Journal of Combinatorics, vol.3, issue.4, pp.633-649, 2012.
DOI : 10.4310/JOC.2012.v3.n4.a3
URL : http://arxiv.org/pdf/1108.0710
, The angel wins. Unpublished, 2007.
, A solution to the Angel Problem, Theoretical Computer Science, vol.389, issue.1-2, pp.152-161, 2007.
DOI : 10.1016/j.tcs.2007.08.006
, The Angel of Power 2 Wins, Combinatorics, Probability and Computing, vol.16, issue.03, pp.363-374, 2007.
DOI : 10.1017/S0963548306008303
, Complexity of connected search when the number of searchers is small In the connected graph searching problem the task is to identify the minimum number of searchers sufficient to clear the graph such that at every step of searching the cleared area is connected. (For a formal definition, please see [1].) While (not connected) graph searching problem is fixed-parameter tractable with a standard parameterization by the number of searchers, for the connected search problem the situation is much more obscure. Can it be that the problem is NP-hard already for small values of searchers like 3 or 4? Similar questions are open for the monotone version of connected search
, Selfish cops and passive robber: Qualitative games, Theoretical Computer Science, vol.680, 2016.
DOI : 10.1016/j.tcs.2017.04.004
URL : http://arxiv.org/abs/1607.05434
, Selfish cops and adversarial robber: Multi-player pursuit evasion on graphs, 2017.
, Stochastic games In Handbook of game theory with economic applications 3, pp.1809-1832, 2002.
, Stochastic games, Encyclopedia of Database Systems, 2009.
URL : https://hal.archives-ouvertes.fr/hal-01492354
, Stochastic games: Recent results, Handbook of game theory with economic applications 3, pp.1833-1850, 2002.
DOI : 10.1016/s1574-0005(02)03011-4
URL : https://hal.archives-ouvertes.fr/hal-00596229
, Fugitive-search games on graphs and related parameters, Theoretical Computer Science, vol.172, issue.12, pp.233-254, 1997.
, A stronger structure theorem for excluded topological minors. arXiv preprint, 2012.
, Constant-factor approximation of the domination number in sparse graphs, European Journal of Combinatorics, vol.34, issue.5, pp.833-840, 2013.
DOI : 10.1016/j.ejc.2012.12.004
, Colouring and Covering Nowhere Dense Graphs, International Workshop on Graph-Theoretic Concepts in Computer Science, pp.325-338
DOI : 10.1016/j.disc.2008.03.024
URL : http://arxiv.org/pdf/1602.05926
, Orderings on graphs and game coloring number. Order, pp.255-264, 2003.
DOI : 10.1023/b:orde.0000026489.93166.cb
, The generalised colouring numbers on classes of bounded expansion, 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, pp.1-8513, 2016.
, Tree-depth, subgraph coloring and homomorphism bounds, European Journal of Combinatorics, vol.27, issue.6, pp.1022-1041, 2006.
DOI : 10.1016/j.ejc.2005.01.010
, Grad and classes with bounded expansion I. Decompositions, European Journal of Combinatorics, vol.29, issue.3, pp.760-776, 2008.
DOI : 10.1016/j.ejc.2006.07.013
, On nowhere dense graphs, European Journal of Combinatorics, vol.32, issue.4, pp.600-617, 2011.
DOI : 10.1016/j.ejc.2011.01.006
, On the generalised colouring numbers of graphs that exclude a fixed minor, Electronic Notes in Discrete Mathematics, vol.49, pp.523-530, 2015.
DOI : 10.1016/j.endm.2015.06.072
, Colouring graphs with bounded generalized colouring number, Discrete Mathematics, vol.309, issue.18, pp.5562-5568, 2009.
DOI : 10.1016/j.disc.2008.03.024
URL : https://doi.org/10.1016/j.disc.2008.03.024