Евристичний удосконалення алгоритму апроксимації лінійного часу для завдання 2-ECSS

  • Спиридон Antonakopoulos Національний технічний університет Афін,
  • Іліас Diakonikolas Національний технічний університет Афін,
Ключові слова: евристичні методи

Анотація

Пропонується декілька евристичних методів поліпшення наближеного алгоритму знаходження мінімального двох-реберного остову заданого графа при збереженні лінійної складності. Така задача частіше за все зустрічається при розробці топології мережі (фізичної або віртуальної), зберігаючої працездатність при відмові однієї з ліній передачі даних. Тестування на випадкових графах різних розмірів і порядків показує, що евристика часто значно зменшує розмір наближеного рішення, в середньому досягаючи відхилення від оптимального рішення не більш, ніж на 1% (в порівнянні з 10% в первинному алгоритмі). Таким чином, ця евристика може мати значну практичну цінність.

Біографії авторів

Спиридон Antonakopoulos, Національний технічний університет Афін,

Школа
Електричні та обчислювальної техніки, кафедра комп'ютерних наук

Іліас Diakonikolas, Національний технічний університет Афін,

Школа
Електричні та обчислювальної техніки, кафедра комп'ютерних наук

Опубліковано
2016-05-30
Як цитувати
[1]
AntonakopoulosС. і DiakonikolasІ., Евристичний удосконалення алгоритму апроксимації лінійного часу для завдання 2-ECSS, ІТКІ, vol 1, № 1, с. 70-73, Трав 2016.