Overview

The longest path problem (LP) is to find a simple path 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.
We proposed an optimal algorithm for solving the longest path problem in undirected graphs. By using graph partitioning and dynamic programming, we designed an algorithm which is significantly faster than other state-of-the-art methods and can solve more instances. Here we provide the implementation of the algorithm as easy to use open source software.

A maze with a longest path.



News:
16th February 2017: Initial Release.
14th February 2017: Published ArXiv Report. Link to PDF.


Licence

The program is licenced under GPL 3.0. Please let us know if you need a commercial licence.
If you publish results using our algorithms, please acknowledge our work by quoting the following paper:

@techreport{balyo2017,
             AUTHOR = {Balyo, Tomas and Fieger, Kai and Schulz, Christian},
             TITLE = {{Optimal Longest Paths by Dynamic Programming}},
             PUBLISHER = {Springer},
             JOURNAL = {Technical Report. arXiv:1702.04170},
             YEAR = {2017}
}

Download

Benchmark Graphs

  • stay tuned!

Support

  • Write us an email if you need support!
  • We are glad for any comments and error reports (or even bug fixes or feature requests) that you send us.
  • Graphs used in our papers will be provided to you on request!