Re: Is register allocation really NP-Complete?

spencert@cs.rpi.edu (Thomas Spencer)
Sun, 31 Mar 91 05:57:38 GMT

          From comp.compilers

Related articles
Is register allocation really NP-Complete? payne@zeus.unomaha.edu (1991-03-26)
Re: Is register allocation really NP-Complete? larus@cs.wisc.edu (1991-03-27)
Re: Is register allocation really NP-Complete? preston@ariel.rice.edu (1991-03-27)
Re: Is register allocation really NP-Complete? david@cs.washington.edu (1991-03-27)
Re: Is register allocation really NP-Complete? preston@ariel.rice.edu (1991-03-28)
Re: Is register allocation really NP-Complete? spencert@cs.rpi.edu (1991-03-31)
| List of all articles for this month |

Newsgroups: comp.compilers
From: spencert@cs.rpi.edu (Thomas Spencer)
Keywords: optimization, theory, design
Organization: Compilers Central
Date: Sun, 31 Mar 91 05:57:38 GMT

Organization: Rensselaer Polytechnic Institute, Troy NY
References: <11422.27ef7017@zeus.unomaha.edu> <15573@june.cs.washington.edu>
Date: 29 Mar 91 02:36:53 GMT


In article <11422.27ef7017@zeus.unomaha.edu> payne@zeus.unomaha.edu (Matt Payne) writes:
>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?


Many register allocation problems have been proven to be NP-complete
without reference to vertex coloring. See:


Sethi, "Complete register allocation problems" SIAM J. of Computing,
1975, pp. 226-248.


and
Garey and Johnson "Computers and Intractibility ..."


--
-Tom Spencer
spencert@turing.cs.rpi.edu
uunet!steinmetz!itsgw!spencert
--


Post a followup to this message

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