Optimal on-line coloring of circular arc graphs
Ślusarek, Maciej
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995), p. 423-429 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1995-01-01
@article{ITA_1995__29_5_423_0,
     author = {\'Slusarek, Maciej},
     title = {Optimal on-line coloring of circular arc graphs},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {29},
     year = {1995},
     pages = {423-429},
     mrnumber = {1360668},
     zbl = {0838.68090},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1995__29_5_423_0}
}

Ślusarek, Maciej. Optimal on-line coloring of circular arc graphs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) pp. 423-429. http://gdmltest.u-ga.fr/item/ITA_1995__29_5_423_0/

1. M. Chrobak and M. Ślusarek, On some packing problem related to dynamic storage allocation, RAIRO Theoretical Informatics and Applications, 1988, 22, pp. 487-499. | Numdam | MR 984588 | Zbl 0675.68041

2. M. R. Garey, D. S. Johnson, G. L. Miller and C. H. Papadimutriou, The complexity of coloring circular arcs and chords, SIAM J. Alg. Disc. Meth., 1980, 1, pp. 216-227. | MR 578325 | Zbl 0499.05058

3. H. A. Kierstead, A polynomial time approximation algorithm for Dynamic Storage Allocation, Discrete Mathematics, 1991, 88, pp. 231-237. | MR 1108016 | Zbl 0761.05087

4. H. A. Kierstead and W. T. Trotter, An extremal problem in recursive combinatorics, Congressus Numerantium, 1981, 33, pp.143-153. | MR 681909 | Zbl 0489.05001

5. M. V. Marathe, H. B. Hunt Iii and S. S. Ravi, Efficient approximation algorithms for Domatic Partition and On-line coloring of Circular Arc Graphs, to appear. Extended abstract in: Proc. Intl. Conf. on Computing and Information ICI'93, Sudbury, May 1993, pp. 26-30.

6. M. Ślusarek, A coloring algorithm for interval graphs, Mathematical Foundations of Computer Science' 89, LNCS 379, pp. 471-480. | MR 1036825 | Zbl 0755.68112