Coarse Grained Parallel Algorithm for Hamiltonian Circuit in Convex Bipartite Graphs

摘要

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v ∈ V, the neighbors of v are consecutive in W. In this work, we address the Hamiltonian Circuit Problem, a well-known problem in Combinatorial Optimization. We present a novel sequential linear-time algorithm for determining a Hamiltonian circuit in convex bipartite graphs which can be easily parallelized. We also describe a coarse grained parallel algorithm for that problem which runs in time O((|V|/p) lg(|V|/p) lg p), for p processors, using O(lg p) communication rounds. We also show how to efficiently implement our solution into PRAM and coarse grained parallel models. Our algorithm provides parallel scalability on commodity clusters. We have made experiments in a cluster composed of 64 processors, obtaining increasing speedups in our implementation. As far as we know, that is the first coarse grained parallel algorithm for the problem.