Главная страница
russian   english
16+
<< назад

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

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


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

Раздел
МАТЕМАТИКА

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

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

Место работы
Алексеев Владимир Евгеньевич
Нижегородский госуниверситет им. Н.И. Лобачевского

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

Захарова Дарья Владимировна
Нижегородский госуниверситет им. Н.И. Лобачевского

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

Мокеев Дмитрий Борисович
Нижегородский госуниверситет им. Н.И. Лобачевского


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

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

Библиографический список
1 . Алексеев В.Е. Наследственные классы и кодирование графов // В сб.: Проблемы кибернетики. Вып. 39. / Под ред. С.В. Яблонского. М.: Наука, 1982. С.151-164.
2 . Алексеев В.Е. Область значений энтропии наследственных классов графов // Дискретная математика. 1992. Т. 4. № 2. С. 148-157.
3 . Алексеев В.Е. О нижних ярусах решетки наследственных классов графов // Дискретный анализ и исследование операций. Серия 1. 1997. Т. 4. С. 3-12.
4 . Алексеев В.Е., Замараев В.А., Лозин В.В., Мэйхил К. // Тез. докл. XV Нижегородской сессии молодых ученых (математические науки). Красный плес, 25-28 мая 2010 г. С. 16-17.
5 . Алексеев В.Е., Захарова Д.В. Независимые множества в графах с ограниченными минорами расширенной матрицы инцидентности // Дискретный анализ и исследование операций. 2010. T. 17. № 1. С. 3-10.
6 . Замараев В.А. Оценка числа графов в некоторых наследственных классах // Материалы X Международного семинара «Дискретная математика и её приложения». Москва, 1-6 февраля 2010 г. С. 301- 303.
7 . Малышев Д.С. О минимальных сложных классах графов // Дискретный анализ и исследование операций. 2009. Т. 16. № 6. С. 43-51.
8 . Малышев Д.С. О минимальных сложных элементах решетки наследственных классов графов // Материалы VII Молодежной научной школы по дискретной математике и ее приложениям. Москва, 2009. С. 12-16.
9 . Малышев Д.С. О тупиковых по вычислительной сложности наследственных классах графов // Материалы X Международного семинара «Дискретная математика и ее приложения». Москва, 1-6 февраля 2010. С. 314-316.
10 . Малышев Д.С. Последовательные минимумы решетки наследственных классов графов для задачи о реберном списковом ранжировании // Вестник Нижегородского университета им. Н.И. Лобачевского. 2010. № 4. С. 70-76.
11 . Малышев Д.С. Минимальные сложные классы графов для задачи о реберном списковом ранжировании // Дискетный анализ и исследование операций. 2011. Т. 17. № 1. С. 133-136.
12 . Шевченко В.Н. Качественные вопросы целочисленного программирования. М.: Наука, 1995. 192 с.
13 . 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.
14 . Ding G., Xu Z., Zang W. Packing cycles in graphs, II // Journal of Combinatorial Theory, Ser. B. 2003. V. 87. P. 244-253.
15 . Scheinerman E.R., Zito J. On the size of hereditary classes of graphs // Journal Combinatorial Theory, Ser. B. 1994. V. 61. P. 16-39.