Institute of Theoretical Informatics, Algorithmics II

Parallel Optimal Longest Path Search

  • Subject:Longest Path Parallelization
  • Type:Masterarbeit
  • Date:November 2018
  • Supervisor:

    Tomas Balyo

  • Student:

    Kai Fieger

  • Links:PDF
  • 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.