Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
verfasst von : Douglas E. Carroll, Adam Meyerson, Brian Tagiku
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.