Anzeige
Erschienen in:
02.11.2016 | Original Article
Online edge coloring of paths and trees with a fixed number of colors
Erschienen in: Acta Informatica | Ausgabe 1/2018
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We study a version of online edge coloring, where the goal is to color as many edges as possible using only a given number, k, of available colors. All of our results are with regard to competitive analysis. Previous attempts to identify optimal algorithms for this problem have failed, even for bipartite graphs. Thus, in this paper, we analyze even more restricted graph classes, paths and trees. For paths, we consider \(k=2\), and for trees, we consider any \(k \ge 2\). We prove that a natural greedy algorithm called \({\textsc {First-Fit}}\) is optimal among deterministic algorithms, on paths as well as trees. For paths, we give a randomized algorithm, which is optimal and better than the best possible deterministic algorithm. For trees, we prove that to obtain a better competitive ratio than \({\textsc {First-Fit}}\), the algorithm would have to be both randomized and unfair (i.e., reject edges that could have been colored), and even such algorithms cannot be much better than \({\textsc {First-Fit}}\).