Abstract: Рассматривается задача о связной раскраске вершин графа в пред­ писанные цвета (СПР). Приводится подробный анализ сложности задачи в зависимости от значений четырех параметров: тип графа, максимальная степень графа, максимальная мощность предписания и максимальная частота вхождения цвета в предписания вершин. Для классов входов задачи СПР, определяемых значением четырехмерного характеристического вектора, находится система из восьми базисных классов, три из которых являются минимальными NP-полными, а ос­ тальные пять классов — максимальными полиномиально разреши­ мыми. Доказывается полнота представленной системы, т. е. своди­ мость любого класса входов к одному из восьми базисных классов. По­ казывается связь между задачей СПР и задачами дискретной оптими­ зации: задачей нахождения связных областей обслуживания, задачами построения расписаний на параллельных машинах, задачей нахожде­ ния максимального паросочетания в двудольном гиперграфе, задачей нахождения подсемейств векторов с суммой из заданной области.

Cite: Кононов А.В. , Севастьянов С.В.
О сложности нахождения связной предписанной раскраски вершин графа
Дискретный анализ и исследование операций. 2000. Т.7. №2. С.21-46.

Dates:

Submitted:

Nov 1, 1999

Identifiers: No identifiers

Citing: Пока нет цитирований