Том 15, номер 6, 2008 г., Стр. 3-10
УДК 519.178
В. Е. Алексеев, Д. С. Малышев
Критерий граничности и его применения
Аннотация:
Даётся новое определение граничного класса графов и доказывается критерий граничности. В качестве примера его применения рассматривается класс, состоящий из графов, у которых каждая компонента связности является деревом с не более чем тремя листьями. Известен ряд задач, для которых этот класс является граничным. Получены достаточные условия его граничности и доказано, что он является граничным для задач о наибольшем двудольном подграфе и наибольшем планарном подграфе.
Ключевые слова: вычислительная сложность, граничный класс, задача о наибольшем подграфе.
Алексеев Владимир Евгеньевич 1
Малышев Дмитрий Сергеевич 1
1. Нижегородский государственный университет,
пр. Гагарина, 23, корп. 2, 603950 Н. Новгород, Россия
е-mail: ave@uic.nnov.ru
Статья поступила 16 июня 2008 г.
Исправленный вариант — 1 октября 2008 г.
