Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs.

*(English)*Zbl 0847.68084Summary: We exploit the close relationship between circular arc graphs and interval graphs to design efficient approximation algorithms for NP-hard optimization problems on circular arc graphs. The problems considered here are maximum domatic partition and on-line minimum vertex coloring.

We present a heuristic for the domatic partition problem with a performance 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 guarantees a solution which is within a factor of 2 of the optimal (off-line) value, and we show that no on-line coloring algorithm can achieve a performance 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 guarantee of 4.

We present a heuristic for the domatic partition problem with a performance 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 guarantees a solution which is within a factor of 2 of the optimal (off-line) value, and we show that no on-line coloring algorithm can achieve a performance 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 guarantee of 4.

PDF
BibTeX
XML
Cite

\textit{M. V. Marathe} et al., Discrete Appl. Math. 64, No. 2, 135--149 (1996; Zbl 0847.68084)

Full Text:
DOI

##### References:

[1] | Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029 |

[2] | Bonucelli, M.A., Dominating sets and domatic number of circular arc graphs, Discrete appl. math., 12, 203-213, (1985) · Zbl 0579.05051 |

[3] | Chaitin, C.G., Register allocation and spilling via graph coloring, (), 98-105, 6 |

[4] | Cockayne, E.J.; Hedetniemi, S.T., Towards a theory of domination in graphs, Networks, 7, 247-261, (1977) · Zbl 0384.05051 |

[5] | Garey, M.R.; Johnson, D.S.; Miller, G.L.; Papadimitriou, C.H., The complexity of coloring circular arcs and chords, SIAM J. algebraic discrete methods, 1, 216-227, (1980) · Zbl 0499.05058 |

[6] | Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054 |

[7] | Gupta, U.I; Lee, D.T.; Leung, J.Y.-T., Efficient algorithms for interval graphs and circular arc graphs, Networks, 12, 459-467, (1982) · Zbl 0493.68066 |

[8] | Hunt, H.B.; Marathe, M.V.; Radhakrishnan, V.; Ravi, S.S.; Rosenkrantz, D.J.; Stearns, R.E., A unified approach to approximation schemes for NP-and PSPACE-hard problems for geometric graphs, (), 424-435 |

[9] | Irani, S., Coloring inductive graphs on-line, (), 470-479 |

[10] | Kant, G.; van Leeuwen, J., The file distribution problem for processor networks, () |

[11] | Kierstead, H., A polynomial time approximation algorithm for dynamic storage allocation, Discrete math., 88, 231-237, (1991) · Zbl 0761.05087 |

[12] | Kierstead, H.; Trotter, W., An extremal problem in recursive combinatorics, (), 143-153 |

[13] | Marathe, M.V.; Hunt, H.B.; Ravi, S.S., Geometric heuristics for unit disk graphs, (), 244-249 |

[14] | Marathe, M.V.; Hunt, H.B.; Ravi, S.S., Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs (extended abstract), (), 26-30 |

[15] | Masuda, S.; Nakajima, K., An optimal algorithm for finding a maximum independent set of a circular arc graph, SIAM J. comput., 17, 41-52, (1988) · Zbl 0646.68084 |

[16] | Patterson, D.A., Reduced instruction set computers, Comm. ACM, 28, 8-21, (1985) |

[17] | Slusarek, M., A coloring algorithm for interval graphs, (), 471-480 · Zbl 0755.68112 |

[18] | Slusarek, M., Optimal on-line coloring of circular arc graphs, (1994), Private communication |

[19] | Rao, A.Srinivas; Rangan, C.Pandu, A linear algorithm for domatic number of interval graphs, Inform. process. lett., 33, 29-33, (1989-1990) · Zbl 0685.68062 |

[20] | Supowit, K.J., Decomposing a set of points into chains, with applications to permutation and circle graphs, Inform. process. lett., 21, 229-252, (1985) · Zbl 0586.68034 |

[21] | Tucker, A., Clolouring a family of circular arcs, SIAM J. appl. math., 29, 493-502, (1975) · Zbl 0312.05105 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.