Circular-arc graph coloring: On chords and circuits in the meeting graph

Circular-arc graph coloring: On chords and circuits in the meeting graph

0.00 Avg rating0 Votes
Article ID: iaor20022958
Country: Netherlands
Volume: 136
Issue: 3
Start Page Number: 483
End Page Number: 500
Publication Date: Feb 2002
Journal: European Journal of Operational Research
Authors: , , ,
Keywords: heuristics
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 heuritics 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.

Reviews

Required fields are marked *. Your email address will not be published.