Том 7, серия 1, номер 2, 2000 г., Стр. 21-46
УДК 519.174
А. В. Кононов, С. В. Севастьянов
О сложности нахождения связной предписанной раскраски вершин графа
Аннотация:
Рассматривается задача о связной раскраске вершин графа в предписанные цвета (СПР). Приводится подробный анализ сложности задачи в зависимости от значений четырех параметров: тип графа, максимальная степень графа, максимальная мощность предписания и максимальная частота вхождения цвета в предписания вершин. Для классов входов задачи СПР, определяемых значением четырехмерного характеристического вектора, находится система из восьми базисных классов, три из которых являются минимальными NP-полными, а остальные пять классов – максимальными полиномиально разрешимыми. Доказывается полнота представленной системы, т. е. сводимость любого класса входов к одному из восьми базисных классов. Показывается связь между задачей СПР и задачами дискретной оптимизации: задачей нахождения связных областей обслуживания, задачами построения расписаний на параллельных машинах, задачей нахождения максимального паросочетания в двудольном гиперграфе, задачей нахождения подсемейств векторов с суммой из заданной области.
Табл. 1, ил. 1, библиогр. 7.
Кононов А. В. 1
Севастьянов С. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: seva@math.nsc.ru
Статья поступила 1 ноября 1999 г.
