НЕКОТОРЫЕ РЕЗУЛЬТАТЫ О НАСЛЕДСТВЕННЫХ КЛАССАХ ГРАФОВ |
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. |