Fast Distributed Algorithms for Brooks-Vizing Colourings (Extended Abstract)

David A. Grable
Alessandro Panconesi

December 1997


We give extremely simple and fast randomized ditributed algorithms for computing vertex colourings in triangle-free graphs which use many fewer than tex2html_wrap_inline20 colours, where tex2html_wrap_inline20 denotes the maximum degree of the input network

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.