Home | english  | Impressum | Sitemap | KIT

Shared-Memory Parallel Longest Paths

Shared-Memory Parallel Longest Paths
Forschungsthema:Longest Paths

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