Пошук академічних текстів

Інформація × Реєстраційний номер 0405U003434, Кандидатська дисертація На здобуття к.ф.-м.н. Дата захисту 02-09-2005 Статус Запланована Назва роботи Методи і алгоритми розпізнавання графів на передфрактальність і їх застосування Здобувач Бобильова Олена Володимирівна, Керівник Кісельова Олена Михайлівна Опонент Перепелиця Віталій Опанасович Опонент Канаєва Наталія Миколаївна Опис Дисертаційна работа присвячена вивченню передфрактальних графів. Отримані властивості канонічних передфрактальних графів, що породжені повною n-вершинною затравкою, колесом, зіркою. Досліджені властивості повних неканонічних передфрактальних графів, старі ребра яких не перетинаються, з заданою кількістю вершин, що заміщуються, і повних неканонічних передфрактальних графів з довільною кількістю вершин, що заміщуються, старі ребра яких перетинаються. На основі отриманих властивостей розроблено методи і поліноміальні алгоритми розпізнавання графів на передфрактальність. Вперше побудовані поліноміальні алгоритми розв’язання деяких NP-повних задач на передфрактальних графах (про вершинне покриття, про домінуючу множину, задачі розбиття на ліси, задачі виділення гамільтонового циклу). Розроблено статистично точний та асимптотично ефективний алгоритми виділення діадичного дерева обмеженого ступеню. Дата реєстрації 2005-09-02 Додано в НРАТ 2020-04-04 Закрити