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) |
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
--
Return to the
comp.compilers page.
Search the
comp.compilers archives again.