Jump to : Download | Abstract | Contact | BibTex reference | EndNote reference |

METIVIER-2010-515904

Yves Métivier, John Michael Robson, Nasser Saheb-Djahromi, Akka Zemmari. About Randomised Distributed Graph Colouring and Graph Partition Algorithms. Information and Computation, 208(2):1296-1304, 2010.

Download

Download paper: Follow the link

Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

We present and analyse a very simple randomised distributed vertex colouring algorithm for arbitrary graphs of size $n$ that halts in time $O(\log n)$ with probability $1-o(n^{-1}).$ Each message containing $1$ bit, its bit complexity per channel is $O(\log n)$. >From this algorithm, we deduce and analyse a randomised distributed vertex colouring algorithm for arbitrary graphs of maximum degree $\Delta$ and size $n$ that uses at most $\Delta+1$ colours and halts in time $O(\log n)$ with probability $1-o(n^{-1}).$ We also obtain a partition algorithm for arbitrary graphs of size $n$ that builds a spanning forest in time $O(\log n)$ with probability $1-o(n^{-1})$. We study some parameters such as the number, the size and the radius of trees of the spanning forest

Contact

Yves Métivier
John-Michael Robson
Nasser Saheb-Djahromi
Akka Zemmari

BibTex Reference

@article{METIVIER-2010-515904,
   Author = {Métivier, Yves and Robson, John Michael and Saheb-Djahromi, Nasser and Zemmari, Akka},
   Title = {About Randomised Distributed Graph Colouring and Graph Partition Algorithms},
   Journal = {Information and Computation},
   Volume = {208},
   Number = {2},
   Pages = {1296--1304},
   Year = {2010}
}

EndNote Reference [help]

Get EndNote Reference (.ref)