longest path problem

The longest path problem asks to find a path of maximum length in a given graph. The problem is NP-complete, but there exists an efficient dynamic programming solution for acyclic digraphs. The detour matrix is a real symmetric matrix whose (i, j)th entry is the length of the longest path from vertex i to vertex j. For a traceable graph, longest paths correspond to Hamiltonian paths. Finding a longest path is challenging for stacked book graphs and Apollonian networks.

antipodal graph | Bellman-Ford algorithm | detour index | detour matrix | detour polynomial | graph circumference | Hamiltonian cycle | Hamiltonian path | path polynomial | shortest path problem | traveling salesman problem