Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!decwrl!world!iecc!compilers-sender
From: spencert@cs.rpi.edu (Thomas Spencer)
Newsgroups: comp.compilers
Subject: Re: Is register allocation really NP-Complete?
Keywords: optimization, theory, design
Message-ID: <+=9fwmm@rpi.edu>
Date: 31 Mar 91 05:57:38 GMT
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: spencert@cs.rpi.edu (Thomas Spencer)
Organization: Compilers Central
Lines: 24
Approved: compilers@iecc.cambridge.ma.us

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
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.