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

16+

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

НЕКОТОРЫЕ РЕЗУЛЬТАТЫ О НАСЛЕДСТВЕННЫХ КЛАССАХ ГРАФОВ. II

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

Тип статьи		Коды УДК	519.17
Страницы	115-120	Ключевые слова	наследственный класс графов, запрещенный порожденный подграф, фильтрованный класс графов, энтропия, q-, граф, энтропийно минимальный класс, граничный класс, минимальный сложный класс, задача о реберном списковом ранжировании, упаковки графов, покрытия гра

Авторы

Алексеев Владимир ЕвгеньевичЗахарова Дарья ВладимировнаМалышев Дмитрий СергеевичМокеев Дмитрий БорисовичСорочан Сергей Владимирович

Место работы

Алексеев Владимир Евгеньевич Нижегородский госуниверситет им. Н.И. Лобачевского
Захарова Дарья Владимировна Нижегородский госуниверситет им. Н.И. Лобачевского
Малышев Дмитрий Сергеевич Нижегородский госуниверситет им. Н.И. Лобачевского Национальный исследовательский университет «Высшая школа экономики», Н. Новгород
Мокеев Дмитрий Борисович Нижегородский госуниверситет им. Н.И. Лобачевского Национальный исследовательский университет «Высшая школа экономики», Н. Новгород
Сорочан Сергей Владимирович Нижегородский госуниверситет им. Н.И. Лобачевского

Аннотация

Рассматриваются вопросы асимптотического перечисления наследственных классов графов и их структурного описания, исследуется сложность некоторых задач на таких классах.

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

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

1 . Алексеев В.Е., Замараев В.А., Захарова Д.В., Малышев Д.С., Мокеев Д.Б. Некоторые результаты о наследственных классах графов // Вестник Нижегородского университета им. Н.И. Лобачевского. 2011. № 6. С. 169–173.
2 . Alekseev V.E. On easy and hard hereditary classes of graphs with respect to the independent set problem // Discrete Appl. Math. 2004. V. 132. P. 17–26.
3 . Алексеев В.Е. Область значений энтропии наследственных классов графов // Дискретная математика. 1992. Т. 4. № 2. С. 148–157.
4 . Алексеев В. Е., Сорочан С.В. Об энтропии наследственных классов цветных графов // Дискретная математика. 2000. Т. 12. № 2. С. 99–102.
5 . Сорочан С.В. Об энтропии композиций наследственных классов цветных графов // Дискретный анализ и исследование операций. Серия 1. 2002. Т. 9. № 1. С. 59–83.
6 . Сорочан С.В. О регулярных композициях наследственных классов цветных графов // Дискретный анализ и исследование операций. Серия 1. 2003. Т. 10. № 1. С. 79–104.
7 . Малышев Д.С. О минимальных сложных классах графов // Дискретный анализ и исследование операций. 2009. Т. 16. № 6. С. 43–51.
8 . Малышев Д.С. Последовательные минимумы решетки наследственных классов графов для задачи о реберном списковом ранжировании // Вестник Нижегородского университета им. Н.И. Лобачевского. 2010. № 4. С. 70–76.
9 . Малышев Д.С. Минимальные сложные классы графов для задачи о реберном списковом ранжировании // Дискетный анализ и исследование операций. 2011. Т. 17. № 1. С. 133–136.
10 . Малышев Д.С. Анализ сложности задачи о реберном списковом ранжировании для наследственных классов графов с не более чем тремя запретами // Дискретный анализ и исследование операций. 2012. Т. 19. № 1. С. 74–96.
11 . Малышев Д.С., Алексеев В.Е. Граничные классы для задач о списковом ранжировании относительно лесов // Дискретный анализ и исследование операций. 2011. Т. 18. № 6. С.61–70.
12 . Алексеев В.Е., Мокеев Д.Б. Кёниговы графы относительно 3-путей // Дискретный анализ и исследование операций. 2012. Т. 19. № 4. С. 3–14.