S. Albers and M. R. Henzinger, Exploring Unknown Environments, SIAM Journal on Computing, vol.29, issue.4, pp.1164-1188, 2000.
DOI : 10.1137/S009753979732428X

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

R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovasz, and C. Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, 20th Annual Symposium on Foundations of Computer Science (sfcs 1979), pp.218-223, 1979.
DOI : 10.1109/SFCS.1979.34

N. Alon, F. R. Chung, and R. L. Graham, Routing permutations on graphs via matchings, STOC, pp.583-591, 1993.
DOI : 10.1137/s0895480192236628

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

S. Alpern and S. Gal, Theory of Search Games and Rendezvous, 2003.

A. Bonato and R. Nowakowski, The Game of Cops and Robbers on Graphs, Amer. Math. Soc, vol.61, 2011.
DOI : 10.1090/stml/061

J. Edmonds, Matroids and the greedy algorithm, Mathematical Programming, vol.57, issue.1, pp.127-136, 1971.
DOI : 10.1007/BF01584082

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

URL : http://doi.org/10.1016/j.tcs.2008.02.040

P. Fraigniaud, D. Ilcinkas, G. Peer, A. Pelc, and D. Peleg, Graph exploration by a finite automaton, Theoretical Computer Science, vol.345, issue.2-3, pp.331-344, 2005.
DOI : 10.1016/j.tcs.2005.07.014

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

M. Fürer and B. Raghavachari, Approximating the Minimum-Degree Steiner Tree to within One of Optimal, Journal of Algorithms, vol.17, issue.3, pp.409-423, 1994.
DOI : 10.1006/jagm.1994.1042

M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP- Completeness, 1979.

M. X. Goemans, Minimum Bounded Degree Spanning Trees, 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp.273-282, 2006.
DOI : 10.1109/FOCS.2006.48

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

D. Krizanc and L. Zhang, Many-to-one packed routing via matchings, In COCOON, pp.11-17, 1997.
DOI : 10.1007/bfb0045067

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

P. Panaite and A. Pelc, Exploring Unknown Undirected Graphs, Journal of Algorithms, vol.33, issue.2, pp.281-295, 1999.
DOI : 10.1006/jagm.1999.1043

G. E. Pantziou, A. Roberts, and A. Symvonis, Many-to-many routing on trees via matchings, Theoretical Computer Science, vol.185, issue.2, pp.347-377, 1997.
DOI : 10.1016/S0304-3975(97)00049-2

URL : http://doi.org/10.1016/s0304-3975(97)00049-2

O. Reingold, Undirected connectivity in log-space, Journal of the ACM, vol.55, issue.4, 2008.
DOI : 10.1145/1391289.1391291

L. Zhang, Optimal Bounds for Matching Routing on Trees, SODA, pp.445-453, 1997.
DOI : 10.1137/S0895480197323159

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