Complexity analysis of a decentralised graph colouring algorithm
References (10)
- et al.
The solution of some random NP-hard problems in polynomial expected time
J. Algorithms
(1989) - et al.
Worst-case time bounds for coloring and satisfiability problems
J. Algorithms
(2002) Almost all k-colorable graphs are easy to color
J. Algorithms
(1988)- et al.
A spectral technique for coloring random 3-colorable graphs
SIAM J. Comput.
(1997) - et al.
Computers and Intractability
(1979)
Cited by (29)
Eventually lattice-linear algorithms
2024, Journal of Parallel and Distributed ComputingA learning approach to decentralised beacon scheduling
2016, Ad Hoc NetworksCitation Excerpt :Note that, even in the case of collisions of beacons when certain information cannot be assessed, nodes may be able to obtain the slot selection in their neighbourhood via other neighbours. Therefore, convergence proofs as the one presented in [26] or the extension described in [27], in which an approach based on a flame-front of dissatisfied nodes is considered, are not directly applicable in this case. We have first evaluated the algorithm presented in this work in random unit disk graphs with given characteristics in order to obtain conclusions under controlled settings.
WLAN channel selection without communication
2012, Computer NetworksCitation Excerpt :Then the CFL algorithm converges, with probability one, to a non-interfering channel allocation. We omit our proof of this result [10] and a more detailed analysis [11]. The proof actually provides a partial answer to a further question, namely how quickly the algorithm converges to a non-interfering allocation.
Eventually Lattice-Linear Algorithms
2023, arXivInducing Lattices in Non-Lattice-Linear Problems
2023, Proceedings of the IEEE Symposium on Reliable Distributed Systems