Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs

摘要

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 4/3-approximation for interval graphs and a 3/2-approximation for chordal graphs. We extend our techniques to the problem of minimizing spillage in these graph types.