Coarse Grained Parallel Maximum Independent Set 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. Lipski and Preparata designed a sequential algorithm for computing a maximum matching in a convex bipartite graph. Bose et al. designed a BSP/CGM algorithm for the same problem. In this work we describe a sequential and a BSP/CGM algorithm for finding a maximum inde-pendent set in a convex bipartite graph. The input of our algorithms is a convex bipartite graph G and a maximum matching of G. Under certain assumptions, the sequential algorithm runs in time O(|V|) while, for p processors, the BSP/CGM algorithm runs in time O(|V|/p) using a constant number of communication rounds in which each processor sends and receives messages of size O(V|/p). The sequential algorithm is faster than the previously known algorithm. To the best of our knowledge, the parallel algorithm is the first in the BSP/CGM model for the problem.