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
Complexity of network synchronization, Journal of the ACM, vol.32, issue.4, pp.804-823, 1985. ,
DOI : 10.1145/4221.4227
Network decomposition and locality in distributed computation, 30th Annual Symposium on Foundations of Computer Science ,
DOI : 10.1109/SFCS.1989.63504
Distributed (? + 1)-coloring in linear (in ?) time, Proc. 41st ACM Symp. Theor. Comput. (STOC), pp.111-120, 2009. ,
Deterministic distributed vertex coloring in polylogarithmic time, Proc. 29th ACM Symp. Principles Distrib. Comput. (PODC), pp.410-419, 2010. ,
Sublogarithmic distributed mis algorithm for sparse graphs using nash-williams decomposition, Distrib. Comput, vol.22, pp.5-6, 2010. ,
Distributed deterministic edge coloring using bounded neighborhood independence, Proc. 30th ACM Symp. Principles Distrib. Comput. (PODC), 2011. ,
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
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
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
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
Drawing maps with advice, Proc. 24th Int. Symp. Distrib. Comput. (DISC), pp.328-342, 2010. ,
DOI : 10.1016/j.jpdc.2011.10.004
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
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
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
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. ,
Parallel Symmetry-Breaking in Sparse Graphs, SIAM Journal on Discrete Mathematics, vol.1, issue.4, pp.434-446, 1988. ,
DOI : 10.1137/0401044
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
Distributed verification of minimum spanning trees, Distributed Computing, vol.26, issue.1, pp.253-266, 2007. ,
DOI : 10.1007/s00446-007-0025-1
Proof labeling schemes, Distributed Computing, vol.34, issue.2, pp.215-233, 2010. ,
DOI : 10.1007/s00446-010-0095-3
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
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
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
Tight Fault Locality, SIAM Journal on Computing, vol.30, issue.1, pp.247-268, 2000. ,
DOI : 10.1137/S0097539797319109
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
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
Locality in Distributed Graph Algorithms, SIAM Journal on Computing, vol.21, issue.1, p.193, 1992. ,
DOI : 10.1137/0221015
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
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
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
What Can be Computed Locally?, SIAM Journal on Computing, vol.24, issue.6, pp.1259-1277, 1995. ,
DOI : 10.1137/S0097539793254571
Some simple distributed algorithms for sparse networks, Distributed Computing, vol.14, issue.2, pp.97-100, 2001. ,
DOI : 10.1007/PL00008932
On the Complexity of Distributed Network Decomposition, Journal of Algorithms, vol.20, issue.2, pp.356-374, 1996. ,
DOI : 10.1006/jagm.1996.0017
Distributed computing. A locality-sensitive approach, SIAM Monographs on Discrete Mathematics and Applications, vol.5, issue.343, 2000. ,
DOI : 10.1137/1.9780898719772
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
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
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