Logo BSU

Please use this identifier to cite or link to this item: https://elib.bsu.by/handle/123456789/221833
Title: Построение больших непересекающихся ациклических подграфов в геометрических графах: магистерская диссертация / Сергей Павлович Зязюлькин; БГУ, Факультет прикладной математики и информатики, Кафедра дискретной математики и алгоритмики; науч. рук. Сарванов В. И.
Authors: Зязюлькин, Сергей Павлович
Keywords: ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика
ЭБ БГУ::ОБЩЕСТВЕННЫЕ НАУКИ::Информатика
Issue Date: 2019
Abstract: Магистерская диссертация, 49 с., 13 рис., 11 источников, 1 приложение. Ключевые слова: ГЕОМЕТРИЧЕСКИЙ ГРАФ, НЕПЕРЕСЕКАЮЩЕЕСЯ ОСТОВНОЕ ДЕРЕВО, НАИБОЛЬШИЙ НЕПЕРЕСЕКАЮЩИЙСЯ АЦИКЛИЧЕСКИЙ ПОДГРАФ, ПЕРЕСЕЧЕНИЕ МАТРОИДОВ, АЛГОРИТМ ЧАСТИЧНОГО ПЕРЕБОРА С ОТСЕЧЕНИЯМИ. Объект исследования – проблема построения больших непересекающихся ациклических подграфов в геометрических графах. В частности, исследуются задачи распознавания и построения непересекающегося остовного дерева и наибольшего непересекающегося ациклического подграфа. Цель работы – изучить основные сведения о проблеме построения больших непересекающихся ациклических подграфов в геометрических графах; исследовать классы геометрических графов, допускающие построение непересекающегося остовного дерева за полиномиальное время; разработать точные экспоненциальные алгоритмы построения больших непересекающихся ациклических подграфов в геометрических графах; реализовать разработанные алгоритмы.
URI: http://elib.bsu.by/handle/123456789/221833
Appears in Collections:1-31 81 09 - "Алгоритмы и системы обработки больших объемов информации"

Show full item record Google Scholar



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.