Построение больших непересекающихся ациклических подграфов в геометрических графах: магистерская диссертация / Сергей Павлович Зязюлькин; БГУ, Факультет прикладной математики и информатики, Кафедра дискретной математики и алгоритмики; науч. рук. Сарванов В. И.

Abstract

Магистерская диссертация, 49 с., 13 рис., 11 источников, 1 приложение. Ключевые слова: ГЕОМЕТРИЧЕСКИЙ ГРАФ, НЕПЕРЕСЕКАЮЩЕЕСЯ ОСТОВНОЕ ДЕРЕВО, НАИБОЛЬШИЙ НЕПЕРЕСЕКАЮЩИЙСЯ АЦИКЛИЧЕСКИЙ ПОДГРАФ, ПЕРЕСЕЧЕНИЕ МАТРОИДОВ, АЛГОРИТМ ЧАСТИЧНОГО ПЕРЕБОРА С ОТСЕЧЕНИЯМИ. Объект исследования – проблема построения больших непересекающихся ациклических подграфов в геометрических графах. В частности, исследуются задачи распознавания и построения непересекающегося остовного дерева и наибольшего непересекающегося ациклического подграфа. Цель работы – изучить основные сведения о проблеме построения больших непересекающихся ациклических подграфов в геометрических графах; исследовать классы геометрических графов, допускающие построение непересекающегося остовного дерева за полиномиальное время; разработать точные экспоненциальные алгоритмы построения больших непересекающихся ациклических подграфов в геометрических графах; реализовать разработанные алгоритмы.