R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, 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

O. Amini, F. Giroire, F. Huc, and S. Pérennes, Minimal selectors and fault tolerant networks, Networks, vol.98, issue.4
DOI : 10.1002/net.20326
URL : https://hal.archives-ouvertes.fr/inria-00082015

Y. Azar, A. Z. Broder, A. R. Karlin, N. Linial, and S. Phillips, Biased random walks, Combinatorica, vol.33, issue.1, pp.1-18, 1996.
DOI : 10.1007/BF01300124

R. Baeza-yates, J. Culberson, and G. Rawlins, Searching in the Plane, Information and Computation, vol.106, issue.2, pp.234-252, 1993.
DOI : 10.1006/inco.1993.1054

R. Beraldi, Biased Random Walks in Uniform Wireless Networks, IEEE Transactions on Mobile Computing, vol.8, issue.4, pp.500-513, 2009.
DOI : 10.1109/TMC.2008.151

B. Bollobás, W. Fernandez-de, and L. Vega, The diameter of random regular graphs, Combinatorica, vol.12, issue.2, pp.125-134, 1982.
DOI : 10.1007/BF02579310

V. Bourassa and F. Holt, Swan: Small-world wide area networks, Proceedings of International Conference on Advances in Infrastructure, 2003.

C. Cooper and A. Frieze, The Cover Time of Random Regular Graphs, SIAM Journal on Discrete Mathematics, vol.18, issue.4, pp.728-740, 2005.
DOI : 10.1137/S0895480103428478

C. Cooper, M. E. Dyer, and C. S. Greenhill, Sampling Regular Graphs and a Peer-to-Peer Network, Combinatorics, Probability and Computing, vol.16, issue.04, pp.557-593, 2007.
DOI : 10.1017/S0963548306007978

C. Cooper, A. Frieze, and T. Radzik, Multiple Random Walks in Random Regular Graphs, SIAM Journal on Discrete Mathematics, vol.23, issue.4, 2008.
DOI : 10.1137/080729542

P. Flocchini, B. Mans, and N. Santoro, Sense of direction: Definitions, properties, and classes, Networks, vol.32, issue.3, pp.165-180, 1998.
DOI : 10.1002/(SICI)1097-0037(199810)32:3<165::AID-NET1>3.0.CO;2-I

P. Flocchini, B. Mans, and N. Santoro, Sense of direction in distributed computing, Theor. Comput. Sci, vol.291, issue.1, 2003.

P. Flocchini, A. Roncato, and N. Santoro, Computing on anonymous networks with sense of direction, Theoretical Computer Science, vol.301, issue.1-3, pp.355-379, 2003.
DOI : 10.1016/S0304-3975(02)00592-3

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

J. Friedman, A proof of alon's second eigenvalue conjecture, Proceedings of the thirty-fifth ACM symposium on Theory of computing , STOC '03, pp.720-724, 2003.
DOI : 10.1145/780542.780646

A. M. Frieze, Edge-Disjoint Paths in Expander Graphs, SIAM Journal on Computing, vol.30, issue.6, pp.1790-1801, 2000.
DOI : 10.1137/S0097539700366103

C. S. Greenhill, F. B. Holt, and N. C. Wormald, Expansion properties of a random regular graph after random vertex deletions, European Journal of Combinatorics, vol.29, issue.5, pp.1139-1150, 2008.
DOI : 10.1016/j.ejc.2007.06.021

N. Hanusse, E. Kranakis, and D. Krizanc, Searching with mobile agents in networks with liars, Discrete Applied Mathematics, vol.137, issue.1, pp.69-85, 2004.
DOI : 10.1016/S0166-218X(03)00189-6
URL : https://hal.archives-ouvertes.fr/hal-00307259

N. Hanusse, D. J. Kavvadias, E. Kranakis, and D. Krizanc, Memoryless search algorithms in a network with faulty advice, Theoretical Computer Science, vol.402, issue.2-3, pp.190-198, 2008.
DOI : 10.1016/j.tcs.2008.04.034
URL : https://hal.archives-ouvertes.fr/hal-00341468

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

S. Ikeda, I. Kubo, N. Okumoto, and M. Yamashita, Impact of Local Topological Information on Random Walks on Finite Graphs, Lecture Notes in Computer Science, vol.2719, pp.1054-1067, 2003.
DOI : 10.1007/3-540-45061-0_81

S. Janson, A. Ruci´nskiruci´nski, and T. Luczak, Random Graphs, 2000.
DOI : 10.1002/9781118032718

A. Kaporis, L. M. Kirousis, E. Kranakis, D. Krizanc, Y. Stamatiou et al., Locating Information with Uncertainty in Fully Interconnected Networks with Applications to World Wide Web Information Retrieval, The Computer Journal, vol.44, issue.4, pp.221-229, 2001.
DOI : 10.1093/comjnl/44.4.221

A. R. Karlin and P. Raghavan, Random Walks and Undirected Graph Connectivity: A Survey, Discrete Probability and Algorithms Institute for Mathematics and Its Applications, pp.95-101, 1995.
DOI : 10.1007/978-1-4612-0801-3_7

L. M. Kirousis, E. Kranakis, D. Krizanc, and Y. Stamatiou, Locating Information with Uncertainty in Fully Interconnected Networks, Networks, vol.42, pp.169-180, 2003.
DOI : 10.1007/3-540-40026-5_19

J. M. Kleinberg and R. Rubinfeld, Short paths in expander graphs, Proceedings of 37th Conference on Foundations of Computer Science, pp.86-95, 1996.
DOI : 10.1109/SFCS.1996.548467

M. Kouck´ykouck´y, Universal traversal sequences with backtracking, Journal of Computer and System Sciences, vol.65, issue.4, pp.717-726, 2002.
DOI : 10.1016/S0022-0000(02)00023-5

E. Kranakis and D. Krizanc, Searching with uncertainty, Proc. SIROCCO'99, pp.194-203, 1999.

L. Lovász, Random walks on graphs: A survey, Combinatorics, pp.1-46, 1993.

E. Makover and J. Mcgowan, Regular trees in random regular graphs, 2008.

E. Sotiris, K. V. Nikoletseas, P. G. Palem, M. Spirakis, and . Yung, Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing, Proceedings of the 21st International Colloquium on Automata, Languages and Programming (ICALP), pp.508-519, 1994.

E. Sotiris, P. G. Nikoletseas, and . Spirakis, Expander properties in random regular graphs with edge faults, STACS, pp.421-432, 1995.

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

E. Michael and . Saks, Randomization and derandomization in space bounded computation, IEEE Conference on Computational Complexity, pp.128-149, 1996.

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