EN|RU

Том 18, номер 1, 2011 г., Стр. 70-76

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

Аннотация:
Рассматривается понятие минимального сложного класса графов применительно к задаче о рёберном списковом ранжировании. Для этой задачи исследуется способ получения таких классов и на его основе выявляется новый класс. Показывается полнота некоторой совокупности классов графов как системы минимальных сложных классов, которые можно получить в рамках предлагаемого подхода.
Библиогр. 5.

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

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

Статья поступила 18 июня 2010 г.

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