|
Михайлюк, В. А. Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений [Текст] / В. А. Михайлюк // Кибернетика и системный анализ. – 2016. – Т. 52, № 3. – С. 39-48.
Используются сведения, вводящие и сохраняющие разрыв. Показано, что для множественной реоптимизации задачи о вычислении хроматического числа графа с заданным экспоненциальным множеством оптимальных решений при вставке произвольной вершины с не более чем двумя ребрами, ей инцидентными, а также при удалении произвольной вершины со всеми инцидентными ей ребрами не существует полиномиально приближенной схемы. |