Publikation

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) befindet sich 15th November 18-20 Zhangjiajie China ACM 2015.

Abstrakt

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.

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence