Solving the longest simple path problem with constraint-based techniques

Pham, Quang Dung [Hanoi Universtiy of science and technology] Deville, Yves [UCL]

The longest simple path problem on graphs arises in a variety of context, e.g., information retrieval, VLSI design, robot patrolling. Given an undirected weighted graph G = (V, E), the problem consists of finding the longest simple path (i.e., no vertex occurs more than once) on G. We propose in this paper an exact and a tabu search algorithm for solving this problem. We show that our techniques give competitive results on different kinds of graphs, compared with recent genetic algorithms.