Name
Abstract | ||
|---|---|---|
In compilers register allocation in loops is usually performed by coloring a corresponding circular-arc graph. Generally, the problem of finding the chromatic number of circular-arc graphs is known to be NP-complete. Thus, approximation algorithms should be considered. In this paper we propose heuristics based on decomposition of a so called meeting graph into a set of circuits. We explain the importance of the meeting graph for our solutions and prove properties of our decomposition of the graph into circuits. We derive inequalities relating the number of circuits in the decomposition to the size of the maximum stable set of chords, and present experimental results. Finally, we discuss the quality of our heuristics for circular-arc graph coloring. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0377-2217(01)00058-3 | European Journal of Operational Research |
Keywords | Field | DocType |
Graph theory,Graph coloring,Graph decomposition,Heuristics | Edge coloring,Discrete mathematics,Combinatorics,Line graph,Circle graph,Graph factorization,Null graph,Butterfly graph,Voltage graph,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
136 | 3 | 0377-2217 |
Citations | PageRank | References |
3 | 0.40 | 17 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dominique de Werra | 1 | 495 | 84.31 |
| Christine Eisenbeis | 2 | 304 | 36.26 |
| Sylvain Lelait | 3 | 84 | 6.86 |
| Elena Stöhr | 4 | 64 | 9.52 |