published by Jukka Suomela
in 2014
in Informatics Engineering
and research's language is
English
Download
Abstract in English
Linials seminal result shows that any deterministic distributed algorithm that finds a $3$-colouring of an $n$-cycle requires at least $log^*(n)/2 - 1$ communication rounds. We give a new simpler proof of this theorem.