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

Інформація × Реєстраційний номер 0417U000824, Кандидатська дисертація На здобуття к.т.н. Дата захисту 18-04-2017 Статус Запланована Назва роботи Спосіб багатошляхової маршрутизації в комп'ютерних мережах великої розмірності Здобувач Діброва Михайло Олександрович, Керівник Кулаков Юрій Олексійович Опонент Додонов Олександр Георгійович Опонент Чемерис Олександр Анатолійович Опис Багатошляхова маршрутизація характеризується великою часовою складністю пошуку множини шляхів, що не перетинаються. Часова складність знаходження найкоротшого шляху по алгоритму Дейкстри представляє собою величину O(kN2). При знаходженні k-шляхів часова складність збільшується відповідно в k раз. В зв'язку з цим, для пошуку множини шляхів, що не перетинаються, в рамках цієї роботи був запропонований модифікований метод "гілок та границь". Це досягається за рахунок виключення операцій перебору варіантів формування кожного шляху. В процесі роботи алгоритму у відповідності з методом "гілок та границь" будується дерево рішень, коренем якого є початкова вершина, а листями є вершини, суміжні з кінцевою вершиною. Дата реєстрації 2017-04-18 Додано в НРАТ 2020-04-03 Закрити