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