Наукова періодика України Кібернетика та системний аналіз

Михайлюк В. А. 
Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений / В. А. Михайлюк // Кибернетика и системный анализ. - 2016. - Т. 52, № 3. - С. 39-48. - Режим доступу: http://nbuv.gov.ua/UJRN/KSA_2016_52_3_5
Использованы сведения, вводящие и сохраняющие разрыв. Показано, что для множественной реоптимизации задачи о вычислении хроматического числа графа с заданным экспоненциальным множеством оптимальных решений при вставке произвольной вершины с не более чем двумя ребрами, ей инцидентными, а также при удалении произвольной вершины со всеми инцидентными ей ребрами не существует полиномиально приближенной схемы (PTAS). Такой же результат имеет место для обычной реоптимизации.
  Повний текст PDF - 124.154 Kb    Зміст випуску     Цитування публікації

Цитованість авторів публікації:
  • Михайлюк В.

    • Бібліографічний опис для цитування:

    Михайлюк В. А. Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений / В. А. Михайлюк // Кибернетика и системный анализ. - 2016. - Т. 52, № 3. - С. 39-48. - Режим доступу: http://nbuv.gov.ua/UJRN/KSA_2016_52_3_5.
      Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"
     
    Відділ інформаційно-комунікаційних технологій
    Пам`ятка користувача

    Всі права захищені © Національна бібліотека України імені В. І. Вернадського