|Graph colouring with unlimited colours email@example.com (Andrew Bromage) (2001-09-29)|
|Re: Graph colouring with unlimited colours firstname.lastname@example.org (2001-09-30)|
|From:||Andrew Bromage <email@example.com>|
|Date:||29 Sep 2001 11:01:10 -0400|
|Keywords:||optimize, theory, question|
|Posted-Date:||29 Sep 2001 11:01:10 EDT|
I'm interested in references for graph colouring where the maximum
number of colours is in general unbounded (but should be as small as
possible). I need this for a virtual machine where thousands of
instances of a given program may be running at any given time, so
using one less register may save a lot of memory (which is in short
supply in this particular application).
The simplest algorithm is to repeatedly remove the smallest degree
node and assign it the smallest colour possible (inventing a new
colour if necessary). However, this doesn't in general do as well as
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
I'm also considering a hybrid approach where you choose a "reasonable"
number of colours, colour with spilling, then repeat the algorithm on
the spilled nodes. Has anyone tried this? How well does it work in
the average/worst case?
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.
Thanks in advance, etc.
Return to the
Search the comp.compilers archives again.