Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений
Используются сведения, вводящие и сохраняющие разрыв. Показано, что для множественной реоптимизации задачи о вычислении хроматического числа графа с заданным экспоненциальным множеством оптимальных решений при вставке произвольной вершины с не более чем двумя ребрами, ей инцидентными, а также при уд...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2016 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/133680 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений / В.А. Михайлюк // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 39-48. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862570099539443712 |
|---|---|
| author | Михайлюк, В.А. |
| author_facet | Михайлюк, В.А. |
| citation_txt | Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений / В.А. Михайлюк // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 39-48. — Бібліогр.: 14 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Используются сведения, вводящие и сохраняющие разрыв. Показано, что для множественной реоптимизации задачи о вычислении хроматического числа графа с заданным экспоненциальным множеством оптимальных решений при вставке произвольной вершины с не более чем двумя ребрами, ей инцидентными, а также при удалении произвольной вершины со всеми инцидентными ей ребрами не существует полиномиально приближенной схемы (PTAS). Такой же результат имеет место для обычной реоптимизации.
Використано зведення, що вводять і зберігають розрив. Показано, що для множинної реоптимізаціі задачі про обчислення хроматичного числа графа із заданою експоненціальною множиною оптимальних розв’язків при уставленні довільної вершини з не більш ніж двома ребрами, їй інцидентними, а також при видаленні довільної вершини з усіма інцидентними їй ребрами не існує поліноміально наближеної схеми (PTAS). Такий же результат має місце для звичайної реоптимізаціі.
The author uses gap-introducing and gap-preserving reductions and shows that for multiple reoptimization of the problem of calculating the chromatic number of a graph with a given exponential set of optimal solutions, when an arbitrary vertex with no more than two edges incident to it is inserted as well as when any vertex with all incident edges is deleted, polynomial time approximation scheme (PTAS) does not exist. The same result holds for ordinary reoptimization.
|
| first_indexed | 2025-11-26T02:06:00Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-133680 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-26T02:06:00Z |
| publishDate | 2016 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Михайлюк, В.А. 2018-06-05T05:40:55Z 2018-06-05T05:40:55Z 2016 Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений / В.А. Михайлюк // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 39-48. — Бібліогр.: 14 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/133680 519.854 Используются сведения, вводящие и сохраняющие разрыв. Показано, что для множественной реоптимизации задачи о вычислении хроматического числа графа с заданным экспоненциальным множеством оптимальных решений при вставке произвольной вершины с не более чем двумя ребрами, ей инцидентными, а также при удалении произвольной вершины со всеми инцидентными ей ребрами не существует полиномиально приближенной схемы (PTAS). Такой же результат имеет место для обычной реоптимизации. Використано зведення, що вводять і зберігають розрив. Показано, що для множинної реоптимізаціі задачі про обчислення хроматичного числа графа із заданою експоненціальною множиною оптимальних розв’язків при уставленні довільної вершини з не більш ніж двома ребрами, їй інцидентними, а також при видаленні довільної вершини з усіма інцидентними їй ребрами не існує поліноміально наближеної схеми (PTAS). Такий же результат має місце для звичайної реоптимізаціі. The author uses gap-introducing and gap-preserving reductions and shows that for multiple reoptimization of the problem of calculating the chromatic number of a graph with a given exponential set of optimal solutions, when an arbitrary vertex with no more than two edges incident to it is inserted as well as when any vertex with all incident edges is deleted, polynomial time approximation scheme (PTAS) does not exist. The same result holds for ordinary reoptimization. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений Складність реоптимізації задачі обчислення хроматичного числа графа із заданою множиною оптимальних розв’язків Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions Article published earlier |
| spellingShingle | Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений Михайлюк, В.А. Кибернетика |
| title | Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений |
| title_alt | Складність реоптимізації задачі обчислення хроматичного числа графа із заданою множиною оптимальних розв’язків Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions |
| title_full | Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений |
| title_fullStr | Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений |
| title_full_unstemmed | Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений |
| title_short | Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений |
| title_sort | сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/133680 |
| work_keys_str_mv | AT mihailûkva složnostʹreoptimizaciizadačivyčisleniâhromatičeskogočislagrafaszadannymmnožestvomoptimalʹnyhrešenii AT mihailûkva skladnístʹreoptimízacíízadačíobčislennâhromatičnogočislagrafaízzadanoûmnožinoûoptimalʹnihrozvâzkív AT mihailûkva hardnessofreoptimizationoftheproblemofcalculatingthechromaticnumberofagraphwithagivensetofoptimalsolutions |