EN|RU

Том 18, номер 6, 2011 г., Стр. 61-70

УДК 519.178
Малышев Д. С., Алексеев В. Е.
Граничные классы для задач о списковом ранжировании относительно лесов

Аннотация:
Найдены все граничные классы для задач о списковом ранжировании графов (в вершинном и рёберном вариантах) относительно класса лесов. Это позволяет определить сложностной статус этих задач для любого наследственного класса, определяемого конечным множеством запрещенных подграфов относительно класса лесов.
Библиогр. 9.

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

Малышев Дмитрий Сергеевич 1
Алексеев Владимир Евгеньевич 2

1. Нац. исслед. университет. Высшая школа экономики в Ниж. Новгороде,
ул. Б. Печёрская 25/12, 603155 Н. Новгород, Россия
2. Нижегородский гос. университет им. Н. И. Лобачевского,
пр-т Гагарина, 23, корп. 2, 603950 Н. Новгород, Россия
е-mail: dsmalyshev@rambler.ru, aleve@rambler.ru

Статья поступила 19 января 2011 г.
Исправленный вариант — 9 августа 2011 г.

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