A. +-11a, ]. J. Araujo, V. Campos, F. Giroire, L. Sampaio et al., On the hull number of some graph classes, Electronic Notes in Discrete Mathematics, vol.38, issue.0 8, pp.49-55, 2011.

V. J. Araujo, F. Campos, L. Giroire, R. Sampaio, and . Soares, On the hull number of some graph classes, Theoretical Computer Science, vol.475, issue.0 8, pp.49-55, 2011.
DOI : 10.1016/j.tcs.2012.12.035
URL : https://hal.archives-ouvertes.fr/inria-00635032

B. S. Anand, M. Changat, S. Klav?ar, I. Peterinacp87, ]. S. Arnborg et al., Convex sets in lexicographic products of graphs Complexity of finding embeddings in a k-tree Directed tree-width examples, Graphs and Combinatorics SIAM Journal on Algebraic Discrete Methods Journal of Combinatorial Theory, Series B, vol.28, issue.4, pp.77-84, 1987.

Y. Aumann, O. Etzioni, R. Feldman, and M. Perkowitz, Predicting event sequences: Data mining for prefetching web-pages Aigner and M. Fromme. A game of cops and robbers, Discrete Applied Mathematics, vol.8, issue.103, pp.1-12, 1984.

]. B. Als04 and . Alspach, Searching and sweeping graphs: a brief survey, Le Matematiche, vol.59, issue.12 4, 2004.

O. Amini, F. Mazoit, N. Nisse, and S. Thomassé, Submodular partition functions, Discrete Mathematics, vol.309, issue.20, pp.6000-6008, 2009.
DOI : 10.1016/j.disc.2009.04.033
URL : https://hal.archives-ouvertes.fr/lirmm-00432698

G. J. Araujo, L. Morel, R. Sampaio, V. Soares, and . Weber, Hull number: -free graphs and reduction rules, LAGOS, 2013.
DOI : 10.1016/j.endm.2013.10.011
URL : https://hal.archives-ouvertes.fr/hal-00724120

A. [. Arnborg, ]. D. Proskurowskiazn99, I. Albrecht, A. Zukerman, and . Nicholson, Linear time algorithms for NP-hard problems restricted to partial k-trees, Proceedings of the 16th international joint conference on Artificial intelligence, pp.11-2499, 1989.
DOI : 10.1016/0166-218X(89)90031-0

]. J. Bar06 and . Barát, Directed path-width and monotonicity in digraph searching Baird and A. Bonato. Meyniel's conjecture on the cop number: A survey, Graphs and Combinatorics Journal of Combinatorics, vol.22, issue.32 103, pp.161-172, 2006.

]. A. Burger, E. J. Cockayne, W. R. Ggündlingh, C. M. Mynhardt, J. H. Van-vuuren et al., Infinite order domination in graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, vol.50, pp.179-194, 2004.

A. Beveridge, A. Dudek, A. Frieze, and T. Müller, Cops and Robbers on Geometric Graphs, Combinatorics, Probability and Computing, vol.46, issue.06, pp.816-834
DOI : 10.1016/S0304-3975(00)00411-4

]. D. Bdh-+-12, A. Berwanger, P. Dawar, S. Hunter, J. Kreutzer et al., The dag-width of directed graphs, Journal of Combinatorial Theory, Series B, vol.102, issue.25, pp.900-923, 2012.

L. Barrière, P. Fraigniaud, N. Santoro, and D. M. Thilikos, Connected and internal graph searching, 29th Workshop on Graph Theoretic Concepts in Computer Science (WG), pp.34-45, 2003.

H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks, Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree, Journal of Algorithms, vol.18, issue.2, pp.238-255, 1995.
DOI : 10.1006/jagm.1995.1009

A. Bonato, P. Golovach, G. Hahn, J. Kratochvílbkl13-]-b, G. Bollobás et al., Efficient and constructive algorithms for the pathwidth and treewidth of graphs Cops and robbers in a random graph On the geodetic number and related metric sets in cartesian product graphs Geodetic sets in graphs Canonical labeling of graphs Bollobás and I. Leader. The angel and the devil in three dimensions, Discrete Mathematics Structural Analysis of Complex Networks Proceedings of the fifteenth annual ACM symposium on Theory of computing Bondy and U.S.R. Murty. Graph Theory. Graduate texts in mathematics, pp.5588-5595, 1983.

R. [. Bonato, . Nowakowski-]-l, S. Babel, and . Olariu, The game of cops and robbers on graphs. Student mathematical library On the p-connectedness of graphs -a survey A linear-time algorithm for finding tree-decompositions of small treewidth, Discrete Applied Mathematics SIAM Journal on Computing, vol.95, issue.50, pp.105-9911, 1996.

]. H. Bod98 and . Bodlaender, A partial k-arboretum of graphs with bounded treewidth, The angel game in the plane. Combinatorics, Probability and Computing, pp.1-45, 1998.

G. [. Bhattacharya, S. Paul, . L. Sanyalbst00-]-h, M. J. Bodlaender, D. M. Serna et al., A cops and robber game in multidimensional grids Constructive linear time algorithms for small cutwidth and carving-width, Algorithms and Computation, pp.1745-1751, 1969.

Z. [. Bacsó, . L. Tuzabt97-]-h, D. M. Bodlaender, H. L. Thilikos, D. M. Bodlaender et al., Dominating cliques in p 5 -free graphs Constructive linear time algorithms for branchwidth Computing small search numbers in linear time, Automata, Languages and Programming Parameterized and Exact Computation, pp.303-308, 1990.

]. A. Cay89, G. B. Cayley, S. R. Cagaanan, and . Canoy-jr, A theorem on trees On the hull sets and hull number of the cartesian product of graphs, Quarterly Journal of Mathematics Discrete Mathematics, vol.23, issue.287, pp.376-378, 1889.

C. Cohen, D. Coudert, D. Mazauric, N. Nepomuceno, and N. Nisse, Tradeoffs in process strategy games with application in the wdm reconfiguration problem, Theoretical Computer Science, vol.30, issue.35, pp.4124675-4687, 2011.
URL : https://hal.archives-ouvertes.fr/inria-00495443

J. Chalopin, V. Chepoi, N. Nisse, and Y. Vaxès, Cop and Robber Games When the Robber Can Hide and Ride, SIAM Journal on Discrete Mathematics, vol.25, issue.1, pp.333-359, 2011.
DOI : 10.1137/100784035
URL : https://hal.archives-ouvertes.fr/inria-00482117

. C. Cdd-+-10-]-c, S. Centeno, M. C. Dantas, D. Dourado, J. L. Rautenbach et al., Convex partitions of graphs induced by paths of order three, Discrete Mathematics & Theoretical Computer Science, vol.12, issue.6, pp.175-184, 2010.

. C. Cdp-+-11-]-c, M. C. Centeno, L. D. Dourado, D. Penso, J. L. Rautenbach et al., Irreversible conversion of graphs On the convexity of paths of length two in undirected graphs, Theoretical Computer Science Electronic Notes in Discrete Mathematics, vol.412, issue.581 103, pp.3693-3700, 2008.

]. D. Chm-+-09, F. Coudert, D. Huc, N. Mazauric, J. Nisse et al., Reconfiguration of the routing in wdm networks with two classes of services, Proceedings of the 13th international conference on Optical Network Design and Modeling, ONDM'09, pp.146-151, 2009.

C. J. Cáceres, M. Hernando, I. M. Mora, M. L. Pelayo, and . Puertas, On the geodetic and the hull numbers in strong product graphs, Computers & Mathematics with Applications, vol.60, issue.11, pp.603020-3031, 2010.
DOI : 10.1016/j.camwa.2010.10.001

D. Coudert, F. Huc, D. R. Mazauric-]-s, C. Jr, I. J. Garcescla02-]-n et al., Convex sets under some graph operations Constrained Cops and Robber Convexities related to path properties on graphs The angel problem The monadic second-order logic of graphs : Definable sets of finite graphs Special tree-width and the verification of monadic second-order graph properties, A distributed algorithm for computing the node search number in trees. Algorithmica Graph-Theoretic Concepts in Computer Science FSTTCS, pp.158-190, 1989.

D. Coudert, S. Perennes, Q. Pham, and J. Sereni, Rerouting requests in wdm networks, 7ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'05), pp.17-20, 2005.
URL : https://hal.archives-ouvertes.fr/inria-00429173

M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Annals of Mathematics, vol.164, issue.1, pp.51-229, 2006.
DOI : 10.4007/annals.2006.164.51

P. [. Cook, ]. Seymour, J. Coudert, and . Sereni, Tour merging via branch-decomposition Characterization of graphs and digraphs with small process number, IN- FORMS Journal on Computing Discrete Applied Mathematics, vol.15, issue.3 2CS1111, pp.233-248, 2003.

C. [. Chartrand, P. Wall, and . Zhang, The Convexity Number of a Graph, Graphs and Combinatorics, vol.18, issue.2, pp.209-217, 2002.
DOI : 10.1007/s003730200014

M. C. Dourado, J. G. Gimbel, J. Kratochvíl, F. Protti, J. L. Szwarcfiter-]-p et al., On the computation of the hull number of a graph Irreversible -threshold processes: Graphtheoretical threshold models of the spread of disease and of opinion, Dendris, L.M. Kirousis, and D.M. Thilikos. Fugitive-search games on graphs and related parameters, pp.5668-5674, 1997.

M. Dourado, F. Protti, D. Rautenbach, and J. Szwarcfiter, On the Hull Number of Triangle-Free Graphs, SIAM Journal on Discrete Mathematics, vol.23, issue.4, pp.2163-2172, 2010.
DOI : 10.1137/090751797

M. C. Dourado, F. Protti, D. Rautenbach, and J. L. Szwarcfiter, Some remarks on the geodetic number of a graph, Discrete Mathematics, vol.310, issue.4, pp.832-837, 2010.
DOI : 10.1016/j.disc.2009.09.018

M. C. Dourado, F. Protti, D. Rautenbach, and J. L. Szwarcfiter, On the Convexity Number of Graphs, Graphs and Combinatorics, vol.4, issue.3, pp.333-345, 2012.
DOI : 10.1007/s00373-011-1049-7

F. [. Dourado, J. L. Protti, . Szwarcfiter, S. B. Everett, and . Seidman, Complexity results related to monophonic convexity, Discrete Applied Mathematics, vol.158, issue.12, pp.1268-1274, 1985.
DOI : 10.1016/j.dam.2009.11.016

L. Fan, P. Cao, W. Lin, and Q. Jacobson, Web prefetching between lowbandwidth clients and proxies: potential and performance Nondeterministic graph searching: From pathwidth to treewidth, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, SIGMETRICS '99, pp.178-187, 1999.

. V. Fgg-+-10-]-f, S. Fomin, P. A. Gaspers, D. Golovach, S. Kratsch et al., Parameterized algorithm for eternal vertex cover, Information Processing Letters, vol.110, issue.16, pp.702-706, 2010.

. V. Fgjm-+-12-]-f, F. Fomin, A. Giroire, D. Jean-marie, N. Mazauric et al., To satisfy impatient web surfers is hard, Fun with Algorithms, pp.166-176, 2012.

. V. Fgk-+-10-]-f, P. A. Fomin, J. Golovach, N. Kratochvíl, K. Nisse et al., Cops and robber game without recharging Cops and robber with constraints Improved approximation algorithms for minimum-weight vertex separators Variations on cops and robbers Monotony properties of connected visible graph searching [Fra87] P. Frankl. Cops and robbers in graphs with large girth and cayley graphs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing Convexity in graphs and hypergraphs. SIAM Journal on Algebraic and Discrete Methods Thilikos. Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM Journal on Computing, pp.411-418, 1986.

]. T. Gal67 and . Gallai, Transitiv orientierbare graphen, Acta Mathematica Academiae Scientiarum Hungarica, vol.18, issue.12 2, pp.25-66, 1967.

]. R. Gan12 and . Ganian, Using neighborhood diversity to solve hard problems. CoRR, abs/1201, p.172, 2012.

S. [. Goddard, S. T. Hedetniemi, and . Hedetniemi, Eternal security in graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, vol.52, pp.169-180, 2005.

. Ghk-+-10-]-r, P. Ganian, J. Hlin?ný, D. Kneis, J. Meister et al., Are there any good digraph width measures? In Parameterized and Exact Computation Some remarks on the convexity number of a graph, Lecture Notes in Computer Science Graphs and Combinatorics, vol.6478, issue.193, pp.135-146357, 2003.

W. [. Goldwasser and . Klostermeyer, Tight bounds for eternal dominating sets in graphs, Discrete Mathematics, vol.308, issue.12, pp.2589-2593, 2008.
DOI : 10.1016/j.disc.2007.06.005

. Gmn-+-13-]-f, D. Giroire, N. Mazauric, S. Nisse, R. Pérennes et al., Connected surveillance game, Sirocco, 2013.

E. [. Goldstein, . Reingoldhk08-]-p, S. Hunter, . Kreutzerhlt93-]-f, E. Harary et al., Digraph measures: Kelly decompositions, games, and orderings The geodetic number of a graph A note on k-cop, l-robber games on graphs Losing the +1 or directed path-width games are monotone, Theoretical Computer Science Theoretical Computer Science Mathematical and Computer Modelling Discrete Mathematics Congressus Numerantium, vol.143, issue.68, pp.93-112206, 1989.

T. Johnson, N. Robertson, P. D. Seymour, R. Thomas, N. Jose et al., Directed Tree-Width, Design of Reliable Communication Networks Proceedings . Fourth International Workshop on Kirousis and Papadimitriou C.H. Interval graphs and searching. Discrete Mathematics, pp.138-154, 1985.
DOI : 10.1006/jctb.2000.2031
URL : http://doi.org/10.1006/jctb.2000.2031

]. B. Kim04, . G. Kimkin92-]-n, and . Kinnersley, A lower bound for the convexity number of some graphs, Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems, USITS'97, pp.185-191, 1992.
DOI : 10.1007/BF02936107

A. Kosowski, B. Li, N. Nisse, and K. Suchan, k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth, Automata, Languages, and Programming Treewidth: Computations and Approximations. Lecture Notes in Computer Science, pp.610-622, 1994.
DOI : 10.1007/978-3-642-31585-5_54
URL : https://hal.archives-ouvertes.fr/hal-00687120

]. O. Klo07, . F. Kloster-]-w, C. M. Klostermeyer, and . Mynhardt, Edge protection in graphs Graphs with equal eternal vertex cover and eternal domination numbers Kanté and L. Nourine. Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs Digraph decompositions and monotonicity in digraph searching, Theoretical Computer Science SOFSEM 2013: Theory and Practice of Computer Science Graph-Theoretic Concepts in Computer Science Kirousis and C.H. Papadimitriou. Searching and pebbling. Theoretical Computer Science, pp.152-161, 1930.

]. A. Lap93 and . Lapaugh, Recontamination does not help to search a graph, Journal of the ACM, vol.40, issue.2, pp.224-245, 1993.

X. [. Lu and . Peng, On Meyniel's conjecture of the cop number, Journal of Graph Theory, vol.38, issue.3, pp.192-205, 2012.
DOI : 10.1002/jgt.20642

]. R. Mö90 and . Möhring, Graph problems related to gate matrix layout and pla folding, Computational Graph Theory, pp.17-51, 1990.

]. R. Mö96, ]. Möhringmá07, and . Máthé, Triangulating graphs without asteroidal triples The angel of power 2 wins [Mam13] M. Mamino. On the computational complexity of a game of cops and robbers, Discrete Applied Mathematics Combinatorics, Probability and Computing Theoretical Computer Science, vol.64, issue.4, pp.281-287, 1996.

. Mhg-+-81-]-n, S. L. Megiddo, M. R. Hakimi, D. S. Garey, C. H. Johnson et al., The complexity of searching a graph, Foundations of Computer Science SFCS '81. 22nd Annual Symposium on, pp.376-385, 1981.

]. J. Mog96, . Mogulms88-]-b, I. H. Monien, and . Sudborough, Hinted caching in the web Min cut is np-complete for edge weighted trees Makedon and I.H. Sudborough. On minimizing width in linear layouts, Proceedings of the 7th workshop on ACM SIGOPS European workshop: Systems support for worldwide applications Nisse and R. Soares. On the monotonicity of process number LAGOS, pp.103-108209, 1988.

P. [. Nowakowski and . Winkler, Vertex-to-vertex pursuit in a graph, Discrete Mathematics, vol.43, issue.2-3, pp.235-239, 1983.
DOI : 10.1016/0012-365X(83)90160-7

. Omk-+-79-]-t, H. Ohtsuki, E. S. Mori, T. Kuh, T. Kashiwabara et al., Onedimensional logic gate assignment and interval graphs. Circuits and Systems Pursuit-evasion in a graph, Theory and Applications of Graphs, pp.675-684, 1979.

J. [. Padmanabhan, Using predictive prefetching to improve World Wide Web latency, ACM SIGCOMM Computer Communication Review, vol.26, issue.3, pp.22-3655, 1983.
DOI : 10.1145/235160.235164

P. [. Robertson and . Seymour, Graph minors. I. Excluding a forest, Journal of Combinatorial Theory, Series B, vol.35, issue.1, pp.39-61, 1983.
DOI : 10.1016/0095-8956(83)90079-5
URL : http://doi.org/10.1006/jctb.1999.1919

P. [. Robertson and . Seymour, Graph minors. X. Obstructions to tree-decomposition, Journal of Combinatorial Theory, Series B, vol.52, issue.2, pp.153-190, 1991.
DOI : 10.1016/0095-8956(91)90061-N

P. [. Robertson and . Seymour, Graph Minors. XX. Wagner's conjecture, Journal of Combinatorial Theory, Series B, vol.92, issue.2, pp.325-357, 1991.
DOI : 10.1016/j.jctb.2004.08.001

]. R. Soa13 and . Soares, Fractional combinatorial games on graphs, Categorical Perspectives 15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), pp.243-263, 2001.

]. F. Sol09, . Solanosp09-]-f, M. Solano, and . Pióro, Analyzing two conflicting objectives of the wdm lightpath reconfiguration problem A mixed-integer programing formulation for the lightpath reconfiguration problem, Proceedings of the Global Communications Conference (GLOBECOM) VIII Workshop on G/MPLS Networks (WGN8), pp.1-7, 2009.

B. [. Scott, . M. Sudakovss13-]-r, J. L. Sampaio, and . Szwarcfiter, A Bound for the Cops and Robbers Problem, Proceedings of the Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS), pp.1438-1442, 1920.
DOI : 10.1137/100812963

R. [. Seymour, . E. Thomastar85-]-r, and . Tarjan, Call routing and the ratcatcher Decomposition by clique separators, Combinatorica Discrete Mathematics, vol.14, issue.552, pp.217-241, 1985.

D. [. Tedder, C. Corneil, M. Habib, and P. , Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations, Automata, Languages and Programming, pp.634-645, 2008.
DOI : 10.1007/978-3-540-70575-8_52

]. D. The08 and . Theis, The cops & robber game on series-parallel graphs. arXiv:0712.2908v2 Algorithms and obstructions for linear-width and related search parameters, Discrete Applied Mathematics, vol.104, issue.43, pp.239-271, 2000.

S. [. Takahashi, Y. Ueno, and . Kajitani, Mixed searching and proper-path-width, Vazirani. Approximation Algorithms, pp.253-268, 1995.
DOI : 10.1016/0304-3975(94)00160-K

Z. Wang, F. X. Lin, L. Zhong, and M. Chishtie, How far can client-only solutions go for mobile browser speed? Directed searching digraphs: Monotonicity and complexity, Proceedings of the 21st international conference on World Wide Web Theory and Applications of Models of Computation, pp.31-40, 2007.

D. [. Yang, B. Dyer, and . Alspach, Sweeping graphs with large clique number, Discrete Mathematics, vol.309, issue.18, pp.5770-5780, 2009.
DOI : 10.1016/j.disc.2008.05.033