An efficient parallel algorithm for the longest path problem in meshes

摘要

In this paper, first we give a sequential linear-time algorithm for thelongest path problem in meshes. This algorithm can be considered as animprovement of [13]. Then based on this sequential algorithm, we present aconstant-time parallel algorithm for the problem which can be run on everyparallel machine.