Shared-Memory Parallel Longest Paths
- Subject:Longest Paths
Tomas Balyo, Christian Schulz
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