|Is register allocation really NP-Complete? email@example.com (1991-03-26)|
|Re: Is register allocation really NP-Complete? firstname.lastname@example.org (1991-03-27)|
|Re: Is register allocation really NP-Complete? email@example.com (1991-03-27)|
|Re: Is register allocation really NP-Complete? firstname.lastname@example.org (1991-03-27)|
|Re: Is register allocation really NP-Complete? email@example.com (1991-03-28)|
|Re: Is register allocation really NP-Complete? firstname.lastname@example.org (1991-03-31)|
|From:||email@example.com (Matt Payne)|
|Keywords:||optimization, theory, design|
|Date:||26 Mar 91 16:00:23 CST|
In the paper "The Priority-Based Coloring Approach to Register
Allocation" by F.C. Chow and J.L. Hennessy in ACM TOPLAS October 1990
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
Please help! Thanks!! -- matt
[Perhaps Chow's algorithm isn't optimal. There are often fast approximate
solutions to NP complete problems -John]
Return to the
Search the comp.compilers archives again.