Shahed University
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.
Files in this item :
Download
Name :
84946_9438010276.pdf
Size :
335Kb
Format :
PDF
Authors' Home page
Fatemeh Keshavarz-Kohjerdi