Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!elroy.jpl.nasa.gov!decwrl!world!iecc!compilers-sender
From: payne@zeus.unomaha.edu (Matt Payne)
Newsgroups: comp.compilers
Subject: Is register allocation really NP-Complete?
Keywords: optimization, theory, design
Message-ID: <11422.27ef7017@zeus.unomaha.edu>
Date: 26 Mar 91 22:00:23 GMT
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: payne@zeus.unomaha.edu (Matt Payne)
Organization: Compilers Central
Lines: 29
Approved: compilers@iecc.cambridge.ma.us

In the paper "The Priority-Based Coloring Approach to Register
Allocation" by F.C.  Chow and J.L.  Hennessy in ACM TOPLAS October 1990
[Chow 90]

States that "Earlier descriptions of the algorithm have not addressed some
other practical issues that arise.  We see three key issues."  "Third, the
running time of the algorithm must be reasonable.  The determination of
whether a graph is r-colorable is NP-complete."

In general this is true, but [Chow 90] describes the interference (or
conflict) graph that is colored to allocate the registers.  [Chow 90]'s
describtion of interference graphs sounds a lot like interval graphs as
described in _Algorithmic Graph Theory and Perfect Graphs_ by M.C.
Golumbic [Golumbic 80].  U.I. Gupta, D.T. Lee, and J.Y.T. Leung "Efficient
algorithms for interval graphs and circular-arc graphs" in Networks 12
(1982), pp.459-467 is supposed to contain a POLYNOMIAL algorithm for
finding the Chromatic Number of an interval graph.  

So, I'm confused.  [Chow 90] implies that this is a NP-complete problem,
but how can it be if [Chow 90]'s interference graphs are interval
graphs?

Please help!   Thanks!! -- matt
payne@zeus.unomaha.edu
[Perhaps Chow's algorithm isn't optimal. There are often fast approximate
solutions to NP complete problems -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.