Search academic texts

Information × Registration Number 0405U003434, Candidate dissertation Status к.ф.-м.н. Date 02-09-2005 popup.evolution o Title The Methods and Algorithms of Recognition of the Graphs on the Prifractile and their Application Author Bobylova Elena Vladimirovna, popup.head Кiseleva Olena Michailivna popup.opponent Перепелиця Віталій Опанасович popup.opponent Канаєва Наталія Миколаївна Description Дисертаційна работа присвячена вивченню передфрактальних графів. Отримані властивості канонічних передфрактальних графів, що породжені повною n-вершинною затравкою, колесом, зіркою. Досліджені властивості повних неканонічних передфрактальних графів, старі ребра яких не перетинаються, з заданою кількістю вершин, що заміщуються, і повних неканонічних передфрактальних графів з довільною кількістю вершин, що заміщуються, старі ребра яких перетинаються. На основі отриманих властивостей розроблено методи і поліноміальні алгоритми розпізнавання графів на передфрактальність. Вперше побудовані поліноміальні алгоритми розв’язання деяких NP-повних задач на передфрактальних графах (про вершинне покриття, про домінуючу множину, задачі розбиття на ліси, задачі виділення гамільтонового циклу). Розроблено статистично точний та асимптотично ефективний алгоритми виділення діадичного дерева обмеженого ступеню. Registration Date 2005-09-02 popup.nrat_date 2020-04-04 Close