Re: Graph colouring with unlimited colours

  Andrew Bromage <bromage@goaway.cc.monash.edu.au> writes:
>The simplest algorithm is to repeatedly remove the smallest degree
>node and assign it the smallest colour possible (inventing a new
>colour if necessary).


Starting with the largest-degree node should yield better results;
small-degree nodes are easier to colour even with some colours already
allocated.


>Has anyone done any work on how badly the "assign a colour to the
>smallest degree node" algorithm works in the average/worst case
>compared with "optimal" colouring? Or has anyone tried some sort of
>delayed colouring algorithm where the number of colours is not fixed
>beforehand?


Look a Steven Vegdahl's paper in the PLDI'99 (pp. 150). He did not
use a fixed number of colours, but rather used a binary search for the
smallest K that the various algorithms succeeded on. Also I think the
small differences between the "merge" results and the "repeated"
results indicate that both are pretty close to optimal. Vegdahls
paper should also answer your question about coalescing and give you
some additional ideas on that.


Also, take a look at the graph colouring literature outside the
compiler community; AFAIK most is published in the Operations Research
literature, and they focus on finding the smallest K.


>Oh, and also, if anyone has any good coalescing heuristics which don't
>depend on choosing a number of colours beforehand, that would be
>extremely helpful too.


Vegdahl's paper should also address this.


- anton
--
M. Anton Ertl Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

Return to the comp.compilers page.
Search the comp.compilers archives again.