B. Awerbuch, M. Betke, R. L. Rivest, and M. Singh, Piecemeal Graph Exploration by a Mobile Robot, Information and Computation, vol.152, issue.2, pp.155-172, 1999.
DOI : 10.1006/inco.1999.2795

B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Poltkin, Network decomposition and locality in distributed computation, 30th Annual Symposium on Foundations of Computer Science, pp.364-369, 1989.
DOI : 10.1109/SFCS.1989.63504

[. Awerbuch, O. Goldreich, R. Vainish, and D. Peleg, A trade-off between information and communication in broadcast protocols, Journal of the ACM, vol.37, issue.2, pp.238-256, 1990.
DOI : 10.1145/77600.77618

S. Abbas, M. Mosbah, and A. Zemmari, Distributed Computation of a Spanning Tree in a Dynamic Graph by Mobile Agents, 2006 IEEE International Conference on Engineering of Intelligent Systems, pp.1-6, 2006.
DOI : 10.1109/ICEIS.2006.1703205

H. Ando, Y. Oasa, I. Suzuki, and M. Yamashita, Distributed memoryless point convergence algorithm for mobile robots with limited visibility, IEEE Transactions on Robotics and Automation, vol.15, issue.5, pp.818-828, 1999.
DOI : 10.1109/70.795787

[. Awerbuch and D. Peleg, Sparse partitions, Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pp.503-513, 1990.
DOI : 10.1109/FSCS.1990.89571

[. Afek and M. Ricklin, Sparser: A Paradigm for Running Distributed Algorithms, Journal of Algorithms, vol.14, issue.2, pp.316-328, 1993.
DOI : 10.1006/jagm.1993.1016

H. Ando, I. Suzuki, and M. Yamashita, Formation and agreement problems for synchronous mobile robots with limited visibility, Proceedings of Tenth International Symposium on Intelligent Control, pp.453-460, 1995.
DOI : 10.1109/ISIC.1995.525098

A. Awerbuch, Complexity of network synchronization, Journal of the ACM, vol.32, issue.4, pp.804-823, 1985.
DOI : 10.1145/4221.4227

I. Belkouch, M. Bui, L. Chen, and A. K. Datta, Self-Stabilizing Deterministic Network Decomposition, Journal of Parallel and Distributed Computing, vol.62, issue.4, pp.696-714, 2002.
DOI : 10.1006/jpdc.2001.1811

P. Lalibarrì-ere, P. Flocchini, N. Fraigniaud, and . Santoro, Can we elect if we cannot compare, 15 th ACM Symp. on Paral. Algo. and Arch. (SPAA'03), pp.324-332, 2003.

L. Barriere, P. Flocchini, P. Fraigniaud, and N. Santoro, Rendezvous and Election of Mobile Agents: Impact of Sense of Direction, Th. of Comp. Sys. (ToCS), pp.143-162, 2007.
DOI : 10.1007/s00224-005-1223-5

L. Blin, P. Fraigniaud, N. Nisse, and S. Vial, Distributed chasing of network intruders, 13 th Colloquium on Structural Information and Communication Complexity (SIROCCO'06), pp.70-84, 2006.
URL : https://hal.archives-ouvertes.fr/hal-01310347

A. Michael, D. K. Bender, and . Slonim, The power of team exploration: two robots can learn unlabeled directed graphs, 35 th IEEE Symp. on Found. of C. Sc, pp.75-85, 1994.

J. Chalopin, E. Godard, Y. Métivier, and R. Ossamy, Mobile Agent Algorithms Versus Message Passing Algorithms, 10 th Int Conf. On Princ. Of Dist. Sys, pp.187-201, 2006.
DOI : 10.1007/11945529_14
URL : https://hal.archives-ouvertes.fr/hal-00308127

J. Czyzowicz, L. G¸asieniecg¸asieniec, and A. Pelc, Gathering few fat mobile robots in the plane, 10 th Intl. Conf. On Principles Of Dist. Sys, pp.350-364, 2006.

C. Cooper, R. Klasing, and T. Radzik, Searching for Black-Hole Faults in a Network Using Multiple Agents, 10 th Intl. Conf. on Principles of Dist. Sys, pp.320-332, 2006.
DOI : 10.1007/11945529_23
URL : https://hal.archives-ouvertes.fr/hal-00307027

[. Das, P. Flocchini, A. Nayak, and N. Santoro, Distributed Exploration of an Unknown Graph, 12 th Colloquium on Structural Information and Communication Complexity, pp.99-114, 2005.
DOI : 10.1007/11429647_10

S. Das, P. Flocchini, A. Nayak, and N. Santoro, Effective Elections for Anonymous Mobile Agents, 17 th Intl. Symp. on Algo. and Computation (ISAAC), pp.732-743, 2006.
DOI : 10.1007/11940128_73

[. Das, P. Flocchini, N. Santoro, and M. Yamashita, Faulttolerant simulation of message-passing algorithms by mobile agents, 14 th Colloquium on Structural Information and Communication Complexity, pp.289-303, 2007.

C. Gavoille, Fast deterministic distributed algorithms for sparse spanners, 13 th Colloquium on Structural Information and Communication Complexity, pp.100-114, 2006.
URL : https://hal.archives-ouvertes.fr/hal-00400435

A. Dessmark and A. Pelc, Optimal graph exploration without good maps, Theoretical Computer Science, vol.326, issue.1-3, pp.343-362, 2004.
DOI : 10.1016/j.tcs.2004.07.031
URL : http://doi.org/10.1016/j.tcs.2004.07.031

M. Fukuda, L. F. Bic, M. B. Dillencourt, and J. M. Cahill, Messages versus Messengers in Distributed Programming, Journal of Parallel and Distributed Computing, vol.57, issue.2, pp.188-211, 1999.
DOI : 10.1006/jpdc.1999.1533

P. Fraigniaud, D. Ilcinkas, and A. Pelc, Oracle size, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing , PODC '06, pp.179-187, 2006.
DOI : 10.1145/1146381.1146410
URL : https://hal.archives-ouvertes.fr/hal-00339854

P. Fraigniaud, D. Ilcinkas, and A. Pelc, Tree Exploration with an Oracle, MFCS, pp.24-37, 2006.
DOI : 10.1007/11821069_2
URL : https://hal.archives-ouvertes.fr/hal-00339868

P. Fraigniaud, A. Korman, and E. Lebhar, Local MST computation with short advice, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures , SPAA '07, pp.154-160, 2007.
DOI : 10.1145/1248377.1248402
URL : https://hal.archives-ouvertes.fr/hal-00154849

[. Flocchini, A. Nayak, and A. Schulz, Decontamination of Arbitrary Networks using a Team of Mobile Agents with Limited Visibility, 6th IEEE/ACIS International Conference on Computer and Information Science (ICIS 2007), pp.469-474, 2007.
DOI : 10.1109/ICIS.2007.87

P. Flocchinia, G. Prencipe, N. Santoro, and P. Widmayer, Gathering of asynchronous robots with limited visibility, Theoretical Computer Science, vol.337, issue.1-3, pp.147-168, 2005.
DOI : 10.1016/j.tcs.2005.01.001

P. Flocchini and N. Santoro, Distributed security algorithms by mobile agents, 8 th Intl. Conf. Dist. Computing and Networking, pp.1-14, 2006.

S. [. Isler, S. Kannan, and . Khanna, Randomized pursuit-evasion with limited visibility, ACM-SIAM Symp. on Discrete Algorithms, pp.1053-1063, 2004.

D. Giorgos, A. A. Kazazakis, and . Argyros, Fast positioning of limited-visibility guards for the inspection of 2d workspaces, IEEE Intl. Conf. on Intelligent Robots and Sys, pp.2843-2848, 2002.

A. Korman and S. Kutten, Labeling Schemes with Queries, 14 th International Colloquium of Structural Information and Communication Complexity (SIROCCO), pp.109-123, 2007.
DOI : 10.1007/978-3-540-72951-8_10

R. Klasing, E. Markou, and A. Pelc, Gathering asynchronous oblivious mobile robots in a ring, Theoretical Computer Science, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00307234

F. Kuhn, T. Moscibroda, and R. Wattenhofer, What cannot be computed locally!, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing , PODC '04, 2004.
DOI : 10.1145/1011767.1011811

F. Kuhn, T. Moscibroda, and R. Wattenhofer, The price of being nearsighted, 17 th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006.

A. Korman, General compact labeling schemes for dynamic trees

S. Kutten and D. Peleg, Fast Distributed Construction of Smallk-Dominating Sets and Applications, Journal of Algorithms, vol.28, issue.1, pp.40-66, 1998.
DOI : 10.1006/jagm.1998.0929

A. Korman, D. Peleg, and Y. Rodeh, Labeling schemes for dynamic tree networks, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, pp.76-87, 2002.

N. Linial, Locality in Distributed Graph Algorithms, SIAM Journal on Computing, vol.21, issue.1, pp.193-201, 1992.
DOI : 10.1137/0221015

S. Moran and S. Snir, Simple and efficient network decomposition and synchronization, Theoretical Computer Science, vol.243, issue.1-2, pp.217-241, 2000.
DOI : 10.1016/S0304-3975(98)00206-0

M. Naor and L. Stockmeyer, What Can be Computed Locally?, SIAM Journal on Computing, vol.24, issue.6, pp.1259-1277, 1995.
DOI : 10.1137/S0097539793254571

I. Pan, F. Lubomir, M. B. Bic, J. J. Dillencourt, M. K. Huseynov et al., Distributed Parallel Computing Using Navigational Programming, International Journal of Parallel Programming, vol.32, issue.1, pp.1-37, 2004.
DOI : 10.1023/B:IJPP.0000015563.36375.17

D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM Monographs on Disc. Math. & Appli, 2000.
DOI : 10.1137/1.9780898719772

A. Panconesi and A. Srinivasan, On the Complexity of Distributed Network Decomposition, Journal of Algorithms, vol.20, issue.2, pp.356-374, 1996.
DOI : 10.1006/jagm.1996.0017

M. Rao, G. Dudek, and S. Whitesides, Minimum Distance Localization for a Robot with Limited Visibility, Proceedings of the 2005 IEEE International Conference on Robotics and Automation, pp.2439-2445, 2005.
DOI : 10.1109/ROBOT.2005.1570478

[. Santoro, Distributed computations by autonomous mobile robots In 28 th Intl. conf. on current trends in theory and practice of c. sc, pp.110-115, 2001.

[. Souissi, X. Défago, and M. Yamashita, Using Eventually Consistent Compasses to Gather Oblivious Mobile Robots with Limited Visibility, 8 th Intl. Symp. on Stabilization, Safety, and Sec.of Dist. Sys, pp.484-500, 2006.
DOI : 10.1007/978-3-540-49823-0_34

I. Centre-de-recherche and . Futurs, Parc Orsay Université -ZAC des Vignes 4, rue Jacques Monod -91893 ORSAY Cedex Centre de recherche INRIA Nancy ? Grand Est : LORIA, Technopôle de Nancy-Brabois -Campus scientifique 615

. Centre-de-recherche-inria-rennes-?-bretagne-atlantique, IRISA, Campus universitaire de Beaulieu -35042 Rennes Cedex Centre de recherche INRIA Grenoble ? Rhône-Alpes : 655, avenue de l'Europe -38334 Montbonnot Saint-Ismier Centre de recherche INRIA Paris ? Rocquencourt : Domaine de Voluceau -Rocquencourt -BP 105 -78153 Le Chesnay Cedex Centre de recherche INRIA Sophia Antipolis ? Méditerranée : 2004, route des Lucioles -BP 93 -06902, 105 -78153 Le Chesnay Cedex (France