Opening book details…
Can I read Using Node Merging to Enhance Graph Coloring on EtoBox?
Using Node Merging to Enhance Graph Coloring by Vegdahl, Steven R. is a Computer Science article available to read on EtoBox.
What is Using Node Merging to Enhance Graph Coloring about?
A Chaitin-style register allocator often blocks during its simplification phase because no node in the interference graph has a degree that is sufficiently small. Typically, this is handled by node-splitting, or by optimistically continuing---and hoping that a legal N-coloring will still be found. We observe that the merging of two nodes in a graph causes a reduction in the degree of any node that had been adjacent to both. We have enhanced Chaitin's coloring algorithm so that it attempts node-merging during graph simplification; this often allows simplification to continue, while still guaranteeing a coloring for the graph. We have tested this algorithm using Appel's database of register-coloring graphs, and have compared it with Chaitin's algorithm. The merge-enhanced algorithm yields a better coloring about 8% of the time, and a worse coloring less than 0.1% of the time.
Who reads Using Node Merging to Enhance Graph Coloring?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Vegdahl, Steven R.
- Publisher
- Association for Computing Machinery; Special Interest Group on Computer Graphics, Association for Computing Machinery; Association for Computing Machinery (ACM) (ISSN 0362-1340)
- Published
- 1999
- Language
- EN
- Field
- Computer Science (Physical Sciences)