Re: Graph colouring with unlimited colours

anton@mips.complang.tuwien.ac.at (Anton Ertl)
30 Sep 2001 22:42:16 -0400

          From comp.compilers

Related articles
Graph colouring with unlimited colours bromage@goaway.cc.monash.edu.au (Andrew Bromage) (2001-09-29)
Re: Graph colouring with unlimited colours anton@mips.complang.tuwien.ac.at (2001-09-30)
| List of all articles for this month |

From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Date: 30 Sep 2001 22:42:16 -0400
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 01-09-131
Keywords: optimize, theory
Posted-Date: 30 Sep 2001 22:42:16 EDT

  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


Post a followup to this message

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