Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений

Используются сведения, вводящие и сохраняющие разрыв. Показано, что для множественной реоптимизации задачи о вычислении хроматического числа графа с заданным экспоненциальным множеством оптимальных решений при вставке произвольной вершины с не более чем двумя ребрами, ей инцидентными, а также при уд...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Кибернетика и системный анализ
Datum:2016
1. Verfasser: Михайлюк, В.А.
Format: Artikel
Sprache:Russisch
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2016
Schlagworte:
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/133680
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Сложность реоптимизации задачи вычисления хроматического числа графа с заданным множеством оптимальных решений / В.А. Михайлюк // Кибернетика и системный анализ. — 2016. — Т. 52, № 3. — С. 39-48. — Бібліогр.: 14 назв. — рос.

Institution

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