Аннотация:
Даётся новое определение граничного класса графов и доказывается критерий граничности. В качестве примера его применения рассматривается класс, состоящий из графов, у которых каждая компонента связности является деревом с не более чем тремя листьями. Известен ряд задач, для которых этот класс является граничным. Получены достаточные условия его граничности и доказано, что он является граничным для задач о наибольшем двудольном подграфе и наибольшем планарном подграфе. Библиогр. 8.
Ключевые слова:вычислительная сложность, граничный класс, задача о наибольшем подграфе.
УДК:519.178
Статья поступила: 16.06.2008 Переработанный вариант: 01.10.2008