|Graph colouring with unlimited colours firstname.lastname@example.org (Andrew Bromage) (2001-09-29)|
|Re: Graph colouring with unlimited colours email@example.com (2001-09-30)|
|From:||firstname.lastname@example.org (Anton Ertl)|
|Date:||30 Sep 2001 22:42:16 -0400|
|Organization:||Institut fuer Computersprachen, Technische Universitaet Wien|
|Posted-Date:||30 Sep 2001 22:42:16 EDT|
Andrew Bromage <email@example.com> 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
>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
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.
M. Anton Ertl Some things have to be seen to be believed
firstname.lastname@example.org Most things have to be believed to be seen
Return to the
Search the comp.compilers archives again.