Re: Short Graph Coloring Question

Sid Ahmed Ali TOUATI <>
13 Apr 2002 23:10:23 -0400

          From comp.compilers

Related articles
Short Graph Coloring Question (Stephen Molloy) (2002-03-31)
Re: Short Graph Coloring Question (Daniel Berlin) (2002-04-06)
Re: Short Graph Coloring Question (Mark Lacey \[MSFT\]) (2002-04-06)
Re: Short Graph Coloring Question (Amal Banerjee) (2002-04-06)
Re: Short Graph Coloring Question (Sid Ahmed Ali TOUATI) (2002-04-13)
| List of all articles for this month |

From: Sid Ahmed Ali TOUATI <>
Newsgroups: comp.compilers
Date: 13 Apr 2002 23:10:23 -0400
Organization: INRIA
References: <> 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 !


Post a followup to this message

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