26 Mar 91 16:00:23 CST

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: | payne@zeus.unomaha.edu (Matt Payne) |

Keywords: | optimization, theory, design |

Organization: | Compilers Central |

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

[Chow 90]

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

graphs?

Please help! Thanks!! -- matt

payne@zeus.unomaha.edu

[Perhaps Chow's algorithm isn't optimal. There are often fast approximate

solutions to NP complete problems -John]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.