Sun, 31 Mar 91 05:57:38 GMT

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.