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

Author(s)

Stefanes, Marco A. ^[1] ; Rubert, Diego P. ^[1] ; Soares, Jose ^[2]

Affiliation

^[1] Univ Fed Mato Grosso do Sul, Fac Comp, Cx Postal 549, BR-79070900 Campo Grande, MS - Brazil

^[2] Univ Sao Paulo, Dept Ciencia Comp, Rua Matao 1010, BR-05508090 Sao Paulo, SP - Brazil

• Document type: Journal article
• Source: THEORETICAL COMPUTER SCIENCE; v. 804, p. 58-71, JAN 12 2020.
• Web of Science Citations: 0

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 nu is an element of V, the neighbors of nu 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((vertical bar V vertical bar/p) lg(vertical bar V vertical bar 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. (C) 2019 Elsevier B.V. All rights reserved. (AU)