Search academic texts

Information × Registration Number 0413U001553, Candidate dissertation Status к.ф.-м.н. Date 22-02-2013 popup.evolution o Title Efficient algorithms for arithmetic graphs Author Grishanovich Tetyana Oleksandrivna, popup.head Provotar Oleksandr Ivanovuch popup.opponent Донець Георгій Панасович popup.opponent Карнаух Тетяна Олександрівна popup.opponent Лялецький Олександр Вадимович Description Дисертація присвячена дослідженню числових графів та ефективних алгоритмів на них. Досліджено теоретичні питання складності алгоритмів. Розглянуто такі підкласи числових графів як арифметичні графи. Доведена актуальність розробки алгоритмів на числових графах. Для таких графів було розроблено та реалізовано на мові програмування новий алгоритм декомпозиції графів за їх вершинами - алгоритм розкладання графів за допомогою їхніх кістяків. Показано, що цей алгоритм забезпечує більшу ефективність за часом як для традиційних способів подання графів, так і для натуральних арифметичних графів. У роботі адаптовано наступні алгоритми відшукання гамільтонових циклів у графах для числових графів: алгоритм із поверненням, Approx-TSP(G), алгоритм із поліноміальним часом. Досліджено характеристики таких алгоритмів. Показано, що числові графи дозволяють покращити оцінки часової складності алгоритмів. Побудовано програмне забезпечення у візуальному середовищі програмування, яке дозволяє розкладати граф за розробленим алгоритмом декомпозиції за умови подання графу у вигляді матриці суміжності та натурального арифметичного графу. А також здійснює відшукання гамільтонових циклів на арифметичних графах, використовуючи адаптовані алгоритми. Registration Date 2013-02-22 popup.nrat_date 2020-04-04 Close