Online Coloring of Comparability Graphs: some resultsReportar como inadecuado

Online Coloring of Comparability Graphs: some results - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Publication date: 2007

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 $O(\sqrt{n})$; furthermore, we devise an algorithm with a competitivity ratio of $\frac{\chi+1}{2}$. For the cocoloring problem, we point out a tight bound of $\frac{n}{4} + \frac{1}{2}$ and we give better bounds in some more restricted cocoloring problems.

Keywords: Online ; Coloring ; Comparability Graphs ; Permutation Graphs Reference ROSE-REPORT-2007-001

Autor: Demange, Marc; Leroy-Beaulieu, Benjamin


Documentos relacionados