Д. С. Малышев, В. Е. Алексеев, “Граничные классы для задач о списковом ранжировании относительно лесов”, Дискретн. анализ и исслед. опер., 2011, том 18, выпуск 6,страницы 61

Эта публикация цитируется в 5 статьях

Граничные классы для задач о списковом ранжировании относительно лесов

Д. С. Малышев^a, В. Е. Алексеев^b

^a Нац. исслед. университет. Высшая школа экономики в Ниж. Новгороде, Н. Новгород, Россия
^b Нижегородский государственный университет им. Н. И. Лобачевского, Н. Новгород, Россия

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

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

УДК: 519.178

Статья поступила: 19.01.2011
Переработанный вариант: 09.08.2011