Tomas Balyo

Kai Fieger

This thesis presents a parallel algorithm that solves the longest path problem for
weighted undirected graphs. The algorithm uses dynamic programming and graph
partitioning in order to find the longest path between two vertices. The algorithm
finds the optimal longest path and not an approximation of it like many other
approaches for NP-complete problems. We first present the serial algorithm and
then how it can be parallelized. Through experiments we measured the speedup of
the parallel algorithm compared to its serial counterpart. We achieved reasonable
speedups. We also demonstrate that the algorithm has possible applications in solving
the Hamiltonian cycle problem.