2009 | OriginalPaper | Chapter
Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
Authors : Douglas E. Carroll, Adam Meyerson, Brian Tagiku
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the problem of aligned coloring of interval and chordal graphs. These problems have substantial applications to register allocation in compilers and have recently been proven NP-Hard. We provide the first constant approximations: a
$\frac{4}{3}$
-approximation for interval graphs and a
$\frac{3}{2}$
-approximation for chordal graphs. We extend our techniques to the problem of minimizing spillage in these graph types.