N. Alon, L. Babai, and A. Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, vol.7, issue.4, pp.567-583, 1986.
DOI : 10.1016/0196-6774(86)90019-2

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

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

L. Barenboim and M. Elkin, Distributed (? + 1)-coloring in linear (in ?) time, Proc. 41st ACM Symp. Theor. Comput. (STOC), pp.111-120, 2009.

L. Barenboim and M. Elkin, Deterministic distributed vertex coloring in polylogarithmic time, Proc. 29th ACM Symp. Principles Distrib. Comput. (PODC), pp.410-419, 2010.

L. Barenboim and M. Elkin, Sublogarithmic distributed mis algorithm for sparse graphs using nash-williams decomposition, Distrib. Comput, vol.22, pp.5-6, 2010.

L. Barenboim and M. Elkin, Distributed deterministic edge coloring using bounded neighborhood independence, Proc. 30th ACM Symp. Principles Distrib. Comput. (PODC), 2011.

J. L. Bentley and A. C. Yao, An almost optimal algorithm for unbounded searching, Information Processing Letters, vol.5, issue.3, pp.82-87, 1976.
DOI : 10.1016/0020-0190(76)90071-5

R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman, and D. Peleg, Label-guided graph exploration by a finite automaton, ACM Transactions on Algorithms, vol.4, issue.4, pp.1-4218, 2008.
DOI : 10.1145/1383369.1383373

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

R. Cole and U. Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing , STOC '86, pp.206-219, 1986.
DOI : 10.1145/12130.12151

B. Derbel, C. Gavoille, D. Peleg, and L. Viennot, On the locality of distributed sparse spanner construction, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, PODC '08, pp.273-282, 2008.
DOI : 10.1145/1400751.1400788

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

D. Dereniowski and A. Pelc, Drawing maps with advice, Proc. 24th Int. Symp. Distrib. Comput. (DISC), pp.328-342, 2010.
DOI : 10.1016/j.jpdc.2011.10.004

P. Fraigniaud, C. Gavoille, D. Ilcinkas, and A. Pelc, Distributed computing with advice: information sensitivity of graph coloring, Distributed Computing, vol.20, issue.2, pp.395-403, 2009.
DOI : 10.1007/s00446-008-0076-y

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

P. Fraigniaud, D. Ilcinkas, and A. Pelc, Communication algorithms with advice, Journal of Computer and System Sciences, vol.76, issue.3-4, pp.222-232, 2010.
DOI : 10.1016/j.jcss.2009.07.002

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

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

P. Fraigniaud, A. Korman, D. Peleg, A. V. Goldberg, and S. A. Plotkin, Local distributed decision Submitted for Publication 17 Efficient parallel algorithms for (? + 1)-coloring and maximal independent set problem, Proc. 19th ACM Symp. Theor. Comput. (STOC), pp.315-324, 1987.

A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, Parallel Symmetry-Breaking in Sparse Graphs, SIAM Journal on Discrete Mathematics, vol.1, issue.4, pp.434-446, 1988.
DOI : 10.1137/0401044

M. Ha´n´ckowiakha´n´ha´n´ckowiak, M. Karo´nskikaro´nski, and A. Panconesi, On the Distributed Complexity of Computing Maximal Matchings, SIAM Journal on Discrete Mathematics, vol.15, issue.1, pp.41-57, 2001.
DOI : 10.1137/S0895480100373121

A. Korman and S. Kutten, Distributed verification of minimum spanning trees, Distributed Computing, vol.26, issue.1, pp.253-266, 2007.
DOI : 10.1007/s00446-007-0025-1

A. Korman, S. Kutten, and D. Peleg, Proof labeling schemes, Distributed Computing, vol.34, issue.2, pp.215-233, 2010.
DOI : 10.1007/s00446-010-0095-3

F. Kuhn, Weak graph colorings, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, SPAA '09, pp.138-144, 2009.
DOI : 10.1145/1583991.1584032

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, pp.300-309, 2004.
DOI : 10.1145/1011767.1011811

F. Kuhn and R. Wattenhofer, On the complexity of distributed graph coloring, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing , PODC '06, pp.7-15, 2006.
DOI : 10.1145/1146381.1146387

S. Kutten and D. Peleg, Tight Fault Locality, SIAM Journal on Computing, vol.30, issue.1, pp.247-268, 2000.
DOI : 10.1137/S0097539797319109

C. Lenzen, Y. Oswald, and R. Wattenhofer, What can be approximated locally?, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, SPAA '08, pp.46-54, 2008.
DOI : 10.1145/1378533.1378540

N. Linial, Distributive graph algorithms Global solutions from local data, 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pp.331-335, 1987.
DOI : 10.1109/SFCS.1987.20

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

Z. Lotker, B. Patt-shamir, and A. Rosén, Distributed Approximate Matching, SIAM Journal on Computing, vol.39, issue.2, pp.445-460, 2009.
DOI : 10.1137/080714403

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

M. Luby, A Simple Parallel Algorithm for the Maximal Independent Set Problem, SIAM Journal on Computing, vol.15, issue.4, pp.1036-1053, 1986.
DOI : 10.1137/0215074

K. Nakano and S. Olariu, Uniform leader election protocols for radio networks, IEEE Transactions on Parallel and Distributed Systems, vol.13, issue.5, pp.516-526, 2002.
DOI : 10.1109/TPDS.2002.1003864

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

A. Panconesi and R. Rizzi, Some simple distributed algorithms for sparse networks, Distributed Computing, vol.14, issue.2, pp.97-100, 2001.
DOI : 10.1007/PL00008932

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

D. Peleg, Distributed computing. A locality-sensitive approach, SIAM Monographs on Discrete Mathematics and Applications, vol.5, issue.343, 2000.
DOI : 10.1137/1.9780898719772

J. Schneider and R. Wattenhofer, A new technique for distributed symmetry breaking, Proceeding of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing, PODC '10, pp.257-266, 2010.
DOI : 10.1145/1835698.1835760

J. Schneider and R. Wattenhofer, An optimal maximal independent set??algorithm for bounded-independence graphs, Distributed Computing, vol.15, issue.1, pp.5-6, 2010.
DOI : 10.1007/s00446-010-0097-1

M. Szegedy and S. Vishwanathan, Locality based graph coloring, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing , STOC '93, pp.201-207, 1993.
DOI : 10.1145/167088.167156