Publication: A hybrid carousel greedy algorithm solving the steiner tree problem with 12 vertices
No Thumbnail Available
Date
2023-05
Journal Title
Journal ISSN
Volume Title
Publisher
Don Mariano Marcos Memorial State Univeristy - South La Union Campus
Abstract
This study dealt with developing a hybrid algorithm (Hybrid Carousel Algorithm)
using the Python programming language, that can effectively solve the Steiner Tree
problem of given graph. It utilizes the Mehlhorn algorithm, an efficient approximation
algorithm based on the original greedy algorithm, that computes near-optimal Steiner
Tree, as substitute to the greedy algorithm in the implementation of the Carousel greedy
algorithm, a heuristic approach developed by Cerrone, Cerulli, & Golden (2017) that
solves optimization problems by iteratively adding edges to a partial solution.
The proposed algorithm was compared to the original implementation of the
Mehlhorn algorithm in terms of their (1) cost, (2) constructed Steiner tree, and (3) runtime
to test the viability of the proposed algorithm in solving the Steiner free problem on a suite
of user-generated graphs, with different cases on selecting the terminals used in each
experiment.
Comparison results showed that the Hybrid Carousel Greedy Algorithm and the
Mehlhorn Algorithm produced similar results in terms of the computed cost and the
constructed Steiner tree. In terms of their average runtime, the proposed algorithm
performed relatively faster than the original algorithm on some a/the experimental set ups
considered, while there were also set ups where the original algorithm outperformed the
proposed algorithm. These differences in average runtimes were also subjected to a
statistical analysis to test whether they are significant or not.
The proposed algorithm was also used 10 solve real-life situations concerning
Steiner trees in the context of Power Distribution Network, and Transportation Network.
Description
Keywords
Citation
Sosing, E. F., De Guzman, A. P. G., & Juguilon, S. L. M. (2023) A hybrid carousel greedy algorithm solving the steiner tree problem with 12 vertices [Unpublished Undergraduate thesis]. Don Mariano Marcos Memorial State Univeristy - South La Union Campus, Agoo, La Union.