AAAI Publications, Twelfth Annual Symposium on Combinatorial Search

Font Size: 
Finding Optimal Longest Paths by Dynamic Programming in Parallel
Kai Fieger, Tomas Balyo, Christian Schulz, Dominik Schreiber

Last modified: 2019-07-05

Abstract


We propose an exact algorithm for solving the longest path problem between two given vertices in undirected weighted graphs. By using graph partitioning and dynamic programming, we obtain an algorithm that is significantly faster than other state-of-the-art methods. This enables us to solve instances that were previously unsolved and solve hard instances significantly faster. We also present a parallel version of the algorithm.

Full Text: PDF