About randomised distributed graph colouring and graph partition algorithms
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. (C) 2010 Published by Elsevier Inc.
colouring graph partition bit complexity randomised distributed graph algorithm probabilistic analysis