EFFICIENT APPROXIMATION ALGORITHMS FOR DOMATIC PARTITION AND ONLINE COLORING OF CIRCULAR ARC GRAPHS

We exploit the close relationship between circular are graphs and inte rval graphs to design efficient approximation algorithms for NP-hard o ptimization problems on circular are graphs. The problems considered h ere are maximum domatic partition and on-line minimum vertex coloring. We present a heuristic for the domatic partition problem with a perfo rmance ratio of 4. For on-line coloring, we consider two different on- line models. In the first model, arcs are presented in the increasing order of their left endpoints. For this model, our heuristic guarantee s a solution which is within a factor of 2 of the optimal (off-line) v alue; and we show that no on-line coloring algorithm can achieve a per formance guarantee of less than 4/3. In the second on-line model, arcs are presented in an arbitrary order; and it is known that no on-line coloring algorithm can achieve a performance guarantee of less than 3. For this model, we present a heuristic which provides a performance g uarantee of 4.