Name
Abstract | ||
|---|---|---|
The Steiner Tree Problem (STP) is a well studied graph theoretic problem. It computes a minimum-weighted tree of a given graph such that the tree spans a given subset of vertices called terminals. STP is NP-hard. Due to its wide applicability, it has been a challenge problem in the 11th DIMACS implementation challenge and the PACE 2018 challenge. Due to its importance, polynomial-time approximation algorithms have been devised for solving the STP. One of the most popular algorithms is by Kou, Markowsky and Berman (KNIB) which provides a 2-approximation to STP. In practice, a naive implementation of the KNIB algorithm is prohibitively slow for large graphs. Our goal in this work is to improve KNIB algorithm's practical utility by parallelizing it on GPU and reduce its execution time on real-world graphs. This parallelization faces several challenges due to the inherent irregular nature of computation, as well as critical design decisions affecting the algorithm choice and optimizations. We overcome these challenges with interesting algorithmic observations and by exploiting parallelization within sub-steps, and develop the first GPU-based efficient approach to computing Steiner trees using KNIB. We illustrate the effectiveness of our approach using several graph benchmarks from the DIMACS Challenge, the PACE Challenge, SteinLib, and SNAP. Our highly optimized GPU implementation achieves an average 20x speedup over the CPU-sequential Open Graph algorithms and Data structure (OGDF)'s KNIB implementation. In addition to this, our optimized CPU implementation achieves an average 4x over OGDF's KNIB, the only published open-source KNIB implementation. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/s10766-021-00723-0 | INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING |
Keywords | DocType | Volume |
Steiner trees, Parallel algorithms, Approximation algorithms, Graphics processing units | Journal | 50 |
Issue | ISSN | Citations |
1 | 0885-7458 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rajesh Pandian Muniasamy | 1 | 0 | 0.34 |
| Rupesh Nasre | 2 | 0 | 0.34 |
| N. S. Narayanaswamy | 3 | 0 | 0.34 |