Re: Short Graph Coloring Question

Sid Ahmed Ali TOUATI <Sid-Ahmed-Ali.TOUATI@inria.fr>
13 Apr 2002 23:10:23 -0400

          From comp.compilers
Related articles
Short Graph Coloring Question chiefwiggum@eircom.net (Stephen Molloy) (2002-03-31)
Re: Short Graph Coloring Question dan@dberlin.org (Daniel Berlin) (2002-04-06)
Re: Short Graph Coloring Question mlacey@microsoft.com (Mark Lacey \[MSFT\]) (2002-04-06)
Re: Short Graph Coloring Question dakupoto@ece.utexas.edu (Amal Banerjee) (2002-04-06)
Re: Short Graph Coloring Question Sid-Ahmed-Ali.TOUATI@inria.fr (Sid Ahmed Ali TOUATI) (2002-04-13)
| List of all articles for this month |
From: Sid Ahmed Ali TOUATI <Sid-Ahmed-Ali.TOUATI@inria.fr>
Newsgroups: comp.compilers
Date: 13 Apr 2002 23:10:23 -0400
Organization: INRIA
References: <Pine.BSI.4.40.0203291645550.1371-100000@tom.iecc.com> 02-03-201
Keywords: registers, optimize
Posted-Date: 13 Apr 2002 23:10:23 EDT

Stephen Molloy wrote:


> Graph Coloring Short Question
>
> Interference Information
>
> Variable | Interferes With
> a | b,c,d,e
> b | a,c,e
> c | a,b,d
> d | a,c
> e | a,b


This example is easy to solve, since your interference graph is derived
from an interval order. Computing an optimal coloring (i.e. looking for
a maximal clique) of such interval graphs can be done in polynomial time
algorithm (O(n log n)), see [Golumbic, 1980]


Here are your intervals


a -------------------
b ----------
c -----------
d -------
e --


In a general case, optimal coloring is NP-complete. Plenty of methods
exist with spill code insertion. google it !


SAAT

Post a followup to this message

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