A. Arenas, L. Danon, A. Díaz-guilera, P. M. Gleiser, and R. Guimerá, Community analysis in social networks, The European Physical Journal B - Condensed Matter, vol.38, issue.2, pp.373-380, 2004.
DOI : 10.1140/epjb/e2004-00130-1

L. Barrì-ere, P. Flocchini, P. Fraigniaud, and N. Santoro, Capture of an intruder by mobile agents, Proc. of the 14th annual ACM Symposium on Parallel Algorithms and Architectures, pp.200-209, 2002.

L. Barrì-ere, P. Fraigniaud, N. Santoro, and D. M. Thilikos, Searching Is Not Jumping, Proc. of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science, pp.34-45, 2003.
DOI : 10.1007/978-3-540-39890-5_4

D. Bienstock, Graph searching, path-width, tree-width and related problems (a survey ), in Reliability of computer and communication networks, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Amer. Math. Soc, vol.5, pp.33-49, 1989.

D. Bienstock and P. Seymour, Monotonicity in graph searching, Journal of Algorithms, vol.12, issue.2, pp.239-245, 1991.
DOI : 10.1016/0196-6774(91)90003-H

L. Blin, P. Fraigniaud, N. Nisse, and S. Vial, Distributed chasing of network intruders, Theoretical Computer Science, vol.399, issue.1-2, pp.12-37, 2008.
DOI : 10.1016/j.tcs.2008.02.004
URL : https://hal.archives-ouvertes.fr/hal-01310347

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.18-238, 1995.
DOI : 10.1006/jagm.1995.1009

H. L. Bodlaender and D. M. Thilikos, Computing Small Search Numbers in Linear Time, Proc. First International Workshop on Parameterized and Exact Computation, pp.37-48, 2004.
DOI : 10.1007/978-3-540-28639-4_4

R. Borchert and N. A. Slade, Bifurcation Ratios and the Adaptive Geometry of Trees, Botanical Gazette, vol.142, issue.3, p.394, 1981.
DOI : 10.1086/337238

R. Breisch, An intuitive approach to speleotopology, Southwestern Cavers (A publication of the Southwestern Region of the, pp.72-78, 1967.

M. R. Fellows and M. A. Langston, Nonconstructive tools for proving polynomial-time decidability, Journal of the ACM, vol.35, issue.3, pp.727-739, 1988.
DOI : 10.1145/44483.44491

P. Flajolet, J. Raoult, and J. Vuillemin, On the average number of registers required for evaluating arithmetic expressions, 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pp.99-125, 1979.
DOI : 10.1109/SFCS.1977.19

P. Flocchini, M. J. Huang, and F. L. Luccio, DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS, International Journal of Foundations of Computer Science, vol.18, issue.03, pp.547-564, 2007.
DOI : 10.1142/S0129054107004838

F. V. Fomin, P. Fraigniaud, and N. Nisse, Nondeterministic graph searching: from pathwidth to treewidth, Algorithmica, pp.53-358, 2009.

F. V. Fomin and D. M. Thilikos, On the monotonicity of games generated by symmetric submodular functions, Discrete Applied Mathematics, vol.131, issue.2, pp.323-335, 2003.
DOI : 10.1016/S0166-218X(02)00459-6

F. V. Fomin and D. M. Thilikos, 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

F. V. Fomin, D. M. Thilikos, and I. Todinca, Connected Graph Searching in Outerplanar Graphs, Electronic Notes in Discrete Mathematics, vol.22, pp.213-216, 2005.
DOI : 10.1016/j.endm.2005.06.032

P. Fraigniaud and N. Nisse, Connected Treewidth and Connected Graph Searching, Proc. of the 7th Latin American Symposium on Theoretical Informatics, pp.479-490, 2006.
DOI : 10.1007/11682462_45
URL : https://hal.archives-ouvertes.fr/inria-00423448

M. Franklin, Z. Galil, and M. Yung, Eavesdropping games: a graph-theoretic approach to privacy in distributed systems, J. Assoc. Comput. Mach, pp.47-225, 2000.

A. Gleyzer, M. Denisyuk, A. Rimmer, and Y. Salingar, A FAST RECURSIVE GIS ALGORITHM FOR COMPUTING STRAHLER STREAM ORDER IN BRAIDED AND NONBRAIDED NETWORKS, Journal of the American Water Resources Association, vol.38, issue.1
DOI : 10.1137/0201010

C. Gotsman, On the Optimality of Valence-based Connectivity Coding, Computer Graphics Forum, vol.46, issue.1, pp.99-102, 2003.
DOI : 10.1006/gmod.2001.0555

G. Gottlob, Z. Miklós, and T. Schwentick, Generalized hypertree decompositions, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems , PODS '07, pp.1-32, 2009.
DOI : 10.1145/1265530.1265533

S. Hoory, N. Linial, and A. Wigderson, Expander graphs and their applications, Bulletin of the American Mathematical Society, vol.43, issue.04, pp.439-561, 2006.
DOI : 10.1090/S0273-0979-06-01126-8
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.134.6788

K. Horsfield, Some mathematical properties of branching trees with application to the respiratory system, Bulletin of Mathematical Biology, vol.1, issue.No. 3, pp.305-315, 1976.
DOI : 10.1007/BF02459562

R. E. Horton, EROSIONAL DEVELOPMENT OF STREAMS AND THEIR DRAINAGE BASINS; HYDROPHYSICAL APPROACH TO QUANTITATIVE MORPHOLOGY, Geological Society of America Bulletin, vol.56, issue.3, pp.275-370, 1945.
DOI : 10.1130/0016-7606(1945)56[275:EDOSAT]2.0.CO;2

F. Huc, Conception de Réseaux Dynamiques Tolérants aux Pannes, 2008.

M. Isenburg, P. Lindstrom, S. Gumhold, and J. Snoeyink, Large mesh simplification using processing sequences, IEEE Transactions on Ultrasonics, Ferroelectrics and Frequency Control, p.61, 2003.
DOI : 10.1109/VISUAL.2003.1250408

N. R. Jennings, An agent-based approach for building complex software systems, Communications of the ACM, vol.44, issue.4, pp.35-41, 2001.
DOI : 10.1145/367211.367250

L. M. Kirousis and C. H. Papadimitriou, Interval graphs and searching, Discrete Math, pp.181-184, 1985.

A. S. Lapaugh, Recontamination does not help to search a graph, Journal of the ACM, vol.40, issue.2, pp.224-245, 1993.
DOI : 10.1145/151261.151263

N. Linial, A. Magen, and M. E. Saks, Trees and Euclidean metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing , STOC '98, pp.169-175, 1998.
DOI : 10.1145/276698.276726
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.793

J. Matou?ek, On embedding trees into uniformly convex Banach spaces, Israel Journal of Mathematics, vol.93, issue.1, pp.221-237, 1999.
DOI : 10.1007/BF02785579

N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou, The complexity of searching a graph, Journal of the ACM, vol.35, issue.1, pp.18-44, 1988.
DOI : 10.1145/42267.42268

R. Mihai and I. Todinca, Pathwidth is NP-Hard for Weighted Trees, Frontiers in Algorithmics, vol.2, issue.2, pp.181-195, 2009.
DOI : 10.1137/0602010
URL : https://hal.archives-ouvertes.fr/hal-00462314

R. H. Möhring, Graph Problems Related to Gate Matrix Layout and PLA Folding, Computational graph theory of Comput, pp.17-51, 1990.
DOI : 10.1007/978-3-7091-9076-0_2

N. Nisse, Connected graph searching in chordal graphs, Discrete Applied Mathematics, vol.157, issue.12, pp.2603-2610, 2009.
DOI : 10.1016/j.dam.2008.08.007
URL : https://hal.archives-ouvertes.fr/hal-00421414

R. J. Nowakowski and N. Zeh, BOUNDARY-OPTIMAL TRIANGULATION FLOODING, International Journal of Computational Geometry & Applications, vol.16, issue.02n03, pp.271-290, 2006.
DOI : 10.1142/S0218195906002038

T. D. Parsons, Pursuit-evasion in a graph, Proc. Internat. Conf., Western Mich, pp.426-441, 1976.
DOI : 10.1007/BFb0070400

N. N. Petrov, A problem of pursuit in the absence of information on the pursued, Differentsial'nye Uravneniya, pp.1345-1352, 1468.

N. Robertson and P. D. 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
URL : http://doi.org/10.1006/jctb.1999.1919

P. D. Seymour and R. Thomas, Call routing and the ratcatcher, Combinatorica, vol.32, issue.2, pp.14-217, 1994.
DOI : 10.1007/BF01215352

A. N. Strahler, HYPSOMETRIC (AREA-ALTITUDE) ANALYSIS OF EROSIONAL TOPOGRAPHY, Geological Society of America Bulletin, vol.63, issue.11, pp.1117-1142, 1952.
DOI : 10.1130/0016-7606(1952)63[1117:HAAOET]2.0.CO;2

A. Takahashi, S. Ueno, and Y. Kajitani, Minimal acyclic forbidden minors for the family of graphs with bounded path-width, Discrete Mathematics, vol.127, issue.1-3, pp.293-304, 1994.
DOI : 10.1016/0012-365X(94)90092-2

B. Yang, D. Dyer, and B. 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

I. Unité-de-recherche-inria-sophia and . Antipolis, route des Lucioles -BP 93 -06902 Sophia Antipolis Cedex (France) Unité de recherche INRIA Futurs : Parc Club Orsay Université -ZAC des Vignes 4, 2004.

I. Unité-de-recherche and . Lorraine, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602 Villers-lès-Nancy Cedex (France) Unité de recherche INRIA Rennes : IRISA, Campus universitaire de Beaulieu -35042 Rennes Cedex (France) Unité de recherche INRIA Rhône-Alpes : 655, avenue de l'Europe -38334 Montbonnot Saint-Ismier (France) Unité de recherche INRIA Rocquencourt, Domaine de Voluceau -Rocquencourt -BP 105 -78153 Le Chesnay Cedex

I. De-voluceau-rocquencourt, BP 105 -78153 Le Chesnay Cedex (France) http://www.inria.fr ISSN, pp.249-6399