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

Пусть задан граф интервалов. Обозначим за <math>\omega</math> размер клики наибольшей кардинальности (полного подграфа) в нем. Графы интервалов обладают тем особым свойством, что в реализации множество вершин клики имеет общую точку, в которой все они пересекаются.

Прежде чем обсуждать онлайн-задачу, необходимо указать некоторые свойства графов интервалов. Существует простой оффлайновый алгоритм, который производит оптимальную раскраску таких графов. Мы говорим, что алгоритм применяет подход First Fit, если каждый раз, когда ему нужно присвоить интервалу цвет, он назначает цвет с наименьшим индексом, который все еще позволяет получить допустимую раскраску. Оптимальный алгоритм просто рассматривает интервалы, отсортированные слева направо по их левым конечным точкам, и применяет подход First Fit. Заметим, что в результирующей раскраске никогда не используется более <math>\omega</math> цветов. И в самом деле, графы интервалов совершенны. //''Граф <math>G</math> является совершенным, если любой индуцированный подграф <math>G</math>, <math>G'</math> (включая <math>G</math>), может быть раскрашен с помощью <math>\omega(G')</math> цветов, где <math>\omega(G')</math> – размер клики наибольшей кардинальности в <math>G'</math>. (Для любого графа <math>\omega</math> является очевидной нижней границей его хроматического числа).''//

Онлайновая раскраска обычно трудна, что относится и к некоторым простым классам графов, таким как деревья. Это связано с нижней границей <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-клешней).