Shared-Memory Parallel Longest Paths

  • Forschungsthema:Longest Paths
  • Typ:Bachelor-/Masterarbeit
  • Betreuer:

    Tomas Balyo, Christian Schulz

Longest Paths

The longest path problem (LP) is to find a simple path (each vertex visited at most once)
of maximum length between two given vertices of a graph where length is defined as the number of edges or the total weight of the edges in the path. The problem is known to be NP-complete and has several applications such as designing circuit boards, project planning, information retrieval or patrolling algorithms for multiple robots in graphs.

Based on recent results, we want to engineer a shared-memory parallel algorithm for the longest paths problem.

You should have:

  • solid knowledge in algorithms and data structures
  • good knowledge in C++ and OpenMP