Registration Number
0506U000313, Doctoral dissertation
Status
д.ф.-м.н.
Date
26-05-2006
popup.evolution
.
Title
Methods and algorithms for solving problems of design network with complex structure
Author
Sharifov Firdovsi Ahun-ogli,
popup.head Shor Naum Zuselevich
popup.opponent Асельдеров Зайнутдін Макашаріпович
popup.opponent Донець Георгій Панасович
popup.opponent Кісельова Олена Михайловна
popup.rada
V.M.Glushkov Institute of Cybernetics of NASU
Description
Дисертація присвячена задачам синтезу мереж з різними обмеженнями на проектованій мережі. У термінах ізоморфізму графів зформульована загальна задача синтезу надійних мереж. Розроблений строго поліноміальний алгоритм для рішення задачі знаходження різних шляхів між джерелом і стоком при виході з ладу одиничного ребра мережі. Запропоновано метод для знаходження точного рішення оцінних задач для загальної задачі розміщення. Доведено, що існує цілочисельне оптимальне рішення задачі атаки для гіперграфів, а також поліноміальна розв'язність задачі атаки для мережі зі зваженими вершинами. Запропонований строго поліноміальний алгоритм рішення найпростішої багатоетапної задачі розміщення на деревоподібної мережі. Доведено поліноміальну розв'язність задачі синтезу мережі які не співпадають, циклами на орієнтованій мережі у випадку, коли різниця ваг довільного ребра дводольного графа можна представити як алгебраїчну суму ваг кінцевих його вершин. Алгоритми знаходження рішень ряду задач, розглянутих у роботі, були використані при рішенні реальних задач. Ключові слова: синтез мереж, ізоморфізм графів, гіперграф, субмодулярна функція, поліматроід, строго поліноміальні алгоритми.
Registration Date
2006-06-06
popup.nrat_date
2020-04-04 / 2026-06-30