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=10.1.1.36.42

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=10.1.1.127.6573

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=10.1.1.69.1767

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=10.1.1.44.229

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=10.1.1.55.7588