Том 16, номер 6, 2009 г., Стр. 43-51

УДК 519.178
Д. С. Малышев
О минимальных сложных классах графов

Аннотация:
Рассматриваются понятия минимального сложного и граничного классов графов. Доказывается, что для задачи распознавания принадлежности наследственному классу графов не существует минимальных сложных классов. Указываются граничные и минимальные сложные классы графов для задач о списковом ранжировании. Эти классы графов являются первыми примерами минимальных сложных классов, а также первыми примерами сложных граничных классов.
Библиогр. 9.

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

Малышев Дмитрий Сергеевич ¹
1. Нижегородский государственный университет,
пр. Гагарина, 23, корп. 2, 603950 Н. Новгород, Россия
е-mail: dsmalyshev@rambler.ru

Статья поступила 10 апреля 2009 г.
Исправленный вариант — 20 июля 2009 г.