An efficient parallel algorithm for the longest path problem in meshes

Fatemeh Keshavarz-Kohjerdi | Alireza Bagheri

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=84946
Date :  2013/08/01
Publish in :    The Journal of Supercomputing
DOI :  https://doi.org/10.1007/s11227-012-0852-0
Link :  https://link.springer.com/content/pdf/10.1007/s11227-012-0852-0.pdf
Keywords :longest

Abstract :

---

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.