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

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

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

N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou, The complexity of searching a graph, J. Assoc. Comput. Mach, pp.35-53, 1988.

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

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

L. M. Kirousis and C. H. Papadimitriou, Searching and pebbling, Theoretical Computer Science, vol.47, pp.205-218, 1986.
DOI : 10.1016/0304-3975(86)90146-5

URL : http://doi.org/10.1016/0304-3975(86)90146-5

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.

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

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

T. D. Parsons, The search number of a connected graph, Proc. of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp.549-554, 1978.

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

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

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

URL : http://doi.org/10.1006/jctb.1999.1919

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

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

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

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

URL : http://dx.doi.org/10.1016/j.disc.2008.05.033

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

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.7198

F. V. Fomin, P. Fraigniaud, and N. Nisse, Nondeterministic Graph Searching: From Pathwidth to Treewidth, Algorithmica, vol.6, issue.1, pp.358-373, 2009.
DOI : 10.1007/s00453-007-9041-6

URL : https://hal.archives-ouvertes.fr/hal-00421420

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

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

N. Robertson and P. D. Seymour, Graph Minors .XIII. The Disjoint Paths Problem, Journal of Combinatorial Theory, Series B, vol.63, issue.1, pp.65-110, 1995.
DOI : 10.1006/jctb.1995.1006

URL : http://doi.org/10.1006/jctb.1999.1919

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

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

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. N. Strahler, Quantitative analysis of watershed geomorphology, Transactions, American Geophysical Union, vol.67, issue.6, pp.913-920, 1957.
DOI : 10.1029/TR038i006p00913

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, pp.40-937, 2004.
DOI : 10.1137/0201010

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

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

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

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

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

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

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

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

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.120.6660

P. Fraigniaud and N. Nisse, Monotony properties of connected visible graph searching, Information and Computation, vol.206, issue.12, pp.1383-1393, 2008.
DOI : 10.1016/j.ic.2008.09.002

URL : https://hal.archives-ouvertes.fr/hal-00421416

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

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

P. Flocchini, M. J. Huang, and F. L. Luccio, Decontamination of hypercubes by mobile agents, Networks, vol.3341, issue.3, pp.167-178, 2008.
DOI : 10.1002/net.20240

D. Ilcinkas, N. Nisse, and D. Soguet, The cost of monotonicity in distributed graph searching, Distributed Computing, vol.410, issue.14, pp.117-127, 2009.
DOI : 10.1007/s00446-009-0089-1

URL : https://hal.archives-ouvertes.fr/hal-00412063

N. Nisse and D. Soguet, Graph searching with advice, Theoretical Computer Science, vol.410, issue.14, pp.1307-1318, 2009.
DOI : 10.1016/j.tcs.2008.08.020

URL : https://hal.archives-ouvertes.fr/inria-00423450

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.

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

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. 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

A. Takahashi, S. Ueno, and Y. Kajitani, Minimal acyclic forbidden minors for the family of graphs with bounded path-width, Disc, Math, vol.127, pp.293-304, 1994.

F. Huc, Conception de Réseaux Dynamiques Tolérants aux Pannes, CNRS -UNSA) INRIA, 2008.

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

D. Dereniowski, From Pathwidth to Connected Pathwidth, 28th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, pp.416-427, 2011.
DOI : 10.1137/110826424

URL : https://hal.archives-ouvertes.fr/hal-00573616

D. Dereniowski, Connected searching of weighted trees, Theoretical Computer Science, vol.412, issue.41, pp.5700-5713, 2011.
DOI : 10.1016/j.tcs.2011.06.017