Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs

Abstract Since bipartite convex graphs emerged from industrial applications, algorithms for this class of graphs have been devised in several research areas such as scheduling, DNA analysis, and constraint programming. 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 describe a coarse grained parallel algorithm for the maximum matching problem in a convex bipartite graph. For p processors, the algorithm runs in O ( ( | V | / p ) lg ⁡ ( | V | / p ) lg ⁡ p ) time and uses O ( lg ⁡ p ) communication rounds. We also address a well-known problem in the area of combinatorial optimization, the Hamiltonian circuit problem, presenting a sequential linear-time algorithm to determine if a convex bipartite graph has a Hamiltonian circuit. We further show how to efficiently implement both algorithms in PRAM and coarse grained parallel models. Experimental tests performed on commercial machines show the algorithms are robust and scalable.