Вестник Нижегородского университета им. Н.И. Лобачевского. Серия: Социальные науки

16+

Название статьи

О СВЯЗИ ПОНЯТИЙ ГРАНИЧНОГО И МИНИМАЛЬНОГО СЛОЖНОГО КЛАССОВ ГРАФОВ

Номер журнала	2
Дата выпуска	2012

Тип статьи	научная статья	Коды УДК	519.17
Страницы	149-151	Ключевые слова	наследственный класс, граничный класс, минимальный сложный класс, задача о списковом ранжировании

Авторы

Малышев Дмитрий Сергеевич

Место работы

Малышев Дмитрий Сергеевич Государственный университет - Высшая школа экономики (Нижегородский филиал), Нижегородский госуниверситет им. Н.И. Лобачевского

Аннотация

Понятия минимального сложного и граничного классов графов являются полезными инструментами при анализе вычислительной сложности задач на графах. Доказывается, что для конечно определенных классов графов эти понятия совпадают. Приводится пример, показывающий, что для бесконечно определенных классов графов это не так.

Загрузить статью

Библиографический список

1 . Алексеев В.Е. Исследование количественных и сложностных характеристик наследственных классов графов: Дисс. … д-ра физ.-мат. наук по специальности 01.01.09 - «Дискретная математика и математическая кибернетика». Нижний Новгород, 2002 г. 116 с.
2 . Малышев Д.С. О минимальных сложных классах графов // Дискретный анализ и исследование операций. 2009. Т. 16. № 6. С. 43-51.
3 . Малышев Д.С. Исследование границ эффективной разрешимости в семействе наследственных классов графов: Дисс. … канд. физ.-мат. наук по специальности 01.01.09 - «Дискретная математика и математическая кибернетика». Нижний Новгород, 2009 г. 113 с.
4 . Малышев Д.С., Алексеев В.Е. Граничные классы графов для задач о списковом ранжировании относительно лесов // Дискретный анализ и исследование операций. 2011. Т. 18. № 6. С. 61-70.
5 . Харари Ф. Теория графов. М.: Мир, 1982.
6 . Alekseev V.E. On easy and hard classes of graphs with respect to the independent set problem // Discrete Applied Mathematics. 2004. V. 132. № 3. P. 17-26.