EN|RU

Том 19, номер 1, 2012 г., Стр. 74-96

УДК 519.178
Малышев Д. С. 
Анализ сложности задачи о рёберном списковом ранжировании для наследственных классов графов с не более чем тремя запретами

Аннотация:
Описаны все наследственные классы графов, определяемые не более чем тремя запрещёнными порождёнными подграфами (обструкциями), для которых задача о рёберном списковом ранжировании полиномиально разрешима. В основе алгоритма распознавания сложностного статуса лежит установление принадлежности обструкций некоторым специальным («критическим») классам графов. Частью множества таких специальных классов являются минимальные по включению наследственные случаи NP-полноты рассматриваемой задачи. Все классы данного типа, определяемые тремя и менее обструкциями, описаны.
Ил. 3, библиогр. 14.

Ключевые слова: вычислительная сложность, минимальный сложный класс, граничный класс, задача о рёберном списковом ранжировании, эффективный алгоритм.

Малышев Дмитрий Сергеевич 1,2
1. Нижегородский гос. университет,
пр. Гагарина, 23, корп. 2, 603950 Нижний Новгород, Россия
2. Национальный исследовательский университет. Высшая школа экономики. (Нижегородский филиал),
ул. Б. Печерская, 25/12, 603155 Нижний Новгород, Россия
е-mail: dsmalyshev@rambler.ru

Статья поступила 31 мая 2011 г.
Исправленный вариант — 2 ноября 2011 г.

 © Институт математики им. С. Л. Соболева, 2015