An efficient parallel algorithm for the longest path problem in meshes

作者：Keshavarz Kohjerdi Fatemeh^*; Bagheri Alireza

来源：Journal of Supercomputing, 2013, 65(2): 723-741.

DOI：10.1007/s11227-012-0852-0

• Grid graph
• Longest path
• Meshes
• Sequential and parallel algorithms

The longest path problem is the problem of finding a simple path with the maximum number of vertices in a given graph, and so far it has been solved polynomially only for a few classes of graphs. This problem generalizes the well-known Hamiltonian path problem, hence it is NP-hard in general graphs. In this paper, first we give a sequential linear-time algorithm for the longest path problem in meshes. Then based on this algorithm, we present a constant-time parallel algorithm for the problem, which can be run on every parallel machine.

• 出版日期2013-8