Онлайн-алгоритм раскраски интервалов: различия между версиями

Онлайновая раскраска обычно трудна, что относится и к некоторым простым классам графов, таким как деревья. Это связано с нижней границей <math>\Omega(log \; n)</math>, полученной Дьярфашем и Лехелем [9] для коэффициента конкурентоспособности онлайн-раскраски деревьев. Существует очень мало классов, для которых известны константные границы. Одним из таких классов являются линейные графы, для которых Бар-Ной, Мотвани и Наор [3] показали, что алгоритм First-Fit является 2-конкурентным (в частности, он использует не более <math>2 \cdot opt - 1</math> цветов, где OPT - количество цветов в оптимальной раскраске), и это наилучший возможный вариант. Позднее этот результат был обобщен на <math>k \cdot opt - k + 1</math> для графов без (k + 1)-клешней в [6] (заметим, что линейные графы являются графами без 3-клешней).