Parallel Algorithms For Steiner Forest

The Steiner Forest Problem is one of the fundamental combinatorial optimization problemsin operations research and computer science. Its applications range from network design to computational biology. Given an undirected graph with non-negative weights for edges and a set of pairs of vertices called terminals, the Steiner Forest Problem is to find the minimum cost subgraph that connects each of the terminal pairs together. The Steiner Forest Problem is APX-hard and NP-hard to approximate within 96/95. Several heuristic and approximation algorithms, with different approximation guarantees, have been proposed for the Steiner Forest Problem. Despite the several research in designing sequential and parallel algorithms to its closely related problem, Steiner Tree Problem, we are not aware of any existing research on the design of parallel algorithms for the Steiner Forest Problem. In this dissertation, we investigated several sequential Steiner Forest algorithms and their performance by an extensive experimental analysis. We also developed a library, called SteinForestLib, consisting of about a thousand of Steiner Forest problem instances, and made it publicly available. We designed a family of parallel algorithms based on a sequential heuristic greedy algorithm called Paired Greedy which iteratively connects the terminal pairs that have the minimum distance. The family of parallel algorithms consists of a set of algorithms exhibiting various degrees of parallelism determined by the numbers of pairs that are connected in parallel in each iteration of the algorithms. Next, we designed a practical parallel approximation algorithm based on the primal-dual sequential algorithm. The parallel algorithm maintains the approximation guarantees of the sequential primal-dual algorithm and it is specifically designed for execution on multi-core computers. We implemented and ran our proposed parallel algorithms on a multi-core system with a large number of cores and perform an extensive experimental performance analysis each of them on Steiner Forest instances from SteinForestLib. We also, compared both proposed parallel algorithms and provided recommendation based on each graph type. The results show that our proposed parallel approximation algorithm achieves a significant speedup with respect to the sequential primal-dual algorithm and outperforms the family of parallel greedy algorithms in most cases