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

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

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

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

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

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

Литература

[1] Алексеев В. Е., Малышев Д. С. Критерий граничности и его применения // Дискрет. анализ и исслед. операций. — 2008. — T. 15, № 6. — C. 3–10.

[2] Малышев Д. С. О минимальных сложных классах графов // Дискрет. анализ и исслед. операций. — 2009. — T. 16, № 6. — C. 43–51.

[3 Малышев Д. С. О минимальных сложных элементах решетки наследственных классов графов // Материалы VII молодёжной научной школы по дискретной математике и её приложениям (Москва, 18–23 мая 2009 г.). Часть II. — М: Изд-во ИПМ РАН, 2009. — C. 12–17.

[4] Малышев Д.С. Исследование границ эффективной разрешимости в семействе наследственных классов графов. Дис. . . . канд. физ-мат. наук: 01.01.09. — Нижний Новгород: ННГУ, 2009. — 113 c.

[5] Alekseev V. E. On easy and hard hereditary classes of graphs with respect to the independent set problem // Discrete Appl. Math. — 2004. — Vol. 132. — P. 17–26.