An efficient parallel algorithm for the longest path problem in meshes |
| |
Authors: | Fatemeh Keshavarz-Kohjerdi Alireza Bagheri |
| |
Affiliation: | 1. Department of Computer Engineering & IT, Amirkabir University of Technology, Tehran, Iran
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|