Skip to main content Skip to main navigation

Publication

Accelerated Steiner Tree Problem Solving on GPU with CUDA

Christian Mathieu; Matthias Klusch
In: Proceedings of the 15th International Conference on Algorithms and Architectures for Parallel Processing. International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP-15), located at 15th, November 18-20, Zhangjiajie, China, ACM, 2015.

Abstract

The Steiner Tree Problem in Graphs (STPG) is an important NP-hard combinatorial optimization problem arising naturally in many applications including network routing, social media analysis, power grid routing and in the context of the semantic web. We present the first parallel heuristics for the solution of the STPG for GPU with CUDA, and show that the achieved speedups for different kinds of graphs are significant compared to one of the fastest serial heuristics STAR.