Оглавление
Введение
1 Критерий тряпичности и его применения
1.1 Терминология и обозначения.
1.1.1 Множества, графы и подграфы.
1.1.2 Множества вершин и метрические характеристики . . . .
1.1.3 Классы графов.
1.2 Пгран и чные классы графов .
1.3 Критерий тряпичности.
1.4 Условия граничиости классов Т и Г
1.4.1 Применение критерия граничиости к рассматриваемым
классам графов
1.4.2 Понятие древесной ширины графа и доказательство достаточного условия граничиости классов ТиБ
1.5 Граничные классы для задачи о наибольшем подграфе.
1.5.1 Задача о реберно наибольшем Хподграфе
1.5.2 Задача о верш и н но наибольшем Хподграфе
1.5.3 Задача о наибольшем связном подграфе
1.5.4 Некоторые замечания.
1.6 Применение понятия древесной ширины к поиску новых случаев граничиости классов Т и Т
1.6.1 Покрытия и разбиения
1.6.2 Множества вершин и рсбер
1.6.3 Задача о нспересекающихся путях
1.6.4 Новые случаи грапичности классов Т и О
1.7 О граничиости классов соТ и соО.
2 НМграничные классы относительно класса планарных графов
2.1 Гипотеза В. Е. Алексеева и ее варианты.
2.1.1 Относительные Пграничиые классы
2.1.2 Рассматриваемый случай
2.2 О сложности задачи НМ в классе планарных графов, не содержащих длинных порожденных путей .
2.3 Полиномиальный алгоритм решения задачи НМ в классе планарных графов без порожденного подграфа .
2.3.1 Некоторые определения и вспомогательные результаты .
2.3.2 Эффективный алгоритм решения задачи НМ в рассматриваемом случае.
2.4 О сложности задачи о независимом множестве в классе планарных графов без порожденного подграфа 71,2,
2.4.1 Планарные графы, не содержащие больших порожденных звезд
2.4.2 Планарные графы без порожденного подграфа Т,к .
2.5 Полиномиальная разрешимость задачи НМ в классе планарных графов, не содержащих больших порожденных яблок
2.5.1 Минорно бсзапексные графы большой древесной ширины
2.5.2 Доказательство основного результата.
3 Оценки мощности множества граничных классов
3.1 Количественные аспекты теории граничных классов
3.2 Задачи с континуальным множеством граничных классов
3.2.1 Задача о вершинной 3раскраске.
3.2.2 Задача о реберной 3раскраске
3.2.3 Некоторые замечания
3.3 Новые случаи полного описания множества относительных граничных классов.
4 Минимальные сложные классы графов
4.1 Вопросы существования минимальных сложных элементов решетки наследственных классов графов
4.2 О несуществовании минимальных сложных классов для некоторых задач теории графов
4.3 Вычислительная сложность задач о списковом ранжировании
в некоторых классах графов
4.4 Минимальные сложные классы графов для задач о списковом ранжировании .
4.4.1 О связях между минимальными сложными и граничными классами.
4.4.2 Наследственные замыкания комет и молотов
4.4.3 Наследственные замыкания звезд и солнц
Литература
- Київ+380960830922