Publication
Online Coloring of Comparability Graphs: some results
Résumé
We study online partitioning of posets from a graph theoretical point of view, which is coloring and cocoloring in comparability graphs. For the coloring problem, we analyse the First-Fit algorithm and show a ratio of ; furthermore, we devise an algorithm with a competitivity ratio of . For the cocoloring problem, we point out a tight bound of and we give better bounds in some more restricted cocoloring problems.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.