Критерий граничности и его применения

Дискретный анализ и исследование операций. 2008. Т. 15. № 6. С. 3–11.

Малышев Д. С., Алексеев В. Е.

Дается новое определение граничного класса графов и доказывается критерий граничности. В качестве примера его применения рассматривается класс, состоящий из графов, у которых каждая компонента связности является деревом с не более чем тремя листьями. Известен ряд задач, для которых этот класс является граничным. Получены достаточные условия его граничности и доказано, что он является граничным для задач о наибольшем двудольном подграфе и наибольшем планарном подграфе.

Ключевые слова: граничный класс, вычислительная сложность, задача о наибольшем подграфе, теория графов