Том 18, номер 1, 2011 г., Стр. 70-76
УДК 519.178
Малышев Д. С.
Минимальные сложные классы графов для задачи о рёберном списковом ранжировании
Аннотация:
Рассматривается понятие минимального сложного класса графов применительно к задаче о рёберном списковом ранжировании. Для этой задачи исследуется способ получения таких классов и на его основе выявляется новый класс. Показывается полнота некоторой совокупности классов графов как системы минимальных сложных классов, которые можно получить в рамках предлагаемого подхода.
Библиогр. 5.
Ключевые слова: вычислительная сложность, минимальный сложный класс, задача о рёберном списковом ранжировании.
Малышев Дмитрий Сергеевич 1,2
1. Нижегородский гос. университет,
пр. Гагарина, 23, корп. 2, 603950 Нижний Новгород, Россия
2.
Гос. университет — высшая школа экономики (Нижегородский филиал),
ул. Б. Печерская, 25/12. 603155 Нижний Новгород, Россия
е-mail: dsmalyshev@rambler.ru
Статья поступила 18 июня 2010 г.
Литература
[1] Малышев Д. С. О минимальных сложных элементах решётки наследственных классов графов // Материалы VII молодёж. науч. шк. по дискрет. математике и её прил. (Москва, 18–23 мая 2009 г.), часть II. — M.: ИПМ РАН, 2009. — C. 12–17.
[2] Малышев Д. С. О минимальных сложных классах графов // Дискрет. анализ и исслед. операций. — 2009. — T. 16, № 6. — С. 43–51.
[3] Малышев Д. С. Последовательные минимумы решетки наследственных классов графов для задачи о рёберном списковом ранжировании // Вестн. Нижегородск. ун-та. — 2010. — №5. — C. 125–130.
[4] Bollobas B. Extremal graph theory. — London: Academic Press, 1978. — 488 p.
[5] Dereniowski D. The complexity of list ranking of trees // Ars Combinatoria. — 2008. — Vol. 86. —
