PARALLEL MAXIMUM INDEPENDENT SET IN CONVEX BIPARTITE GRAPHS

A bipartite graph G = (V, W, E) is called convex if the vertices in W can be ordered in such a way that the elements of W adjacent to any ve rtex nu is an element of V form an interval (i.e. a sequence consecuti vely numbered vertices). Such a graph can be represented in a compact form that requires O(n) space, where n = max{\V\, \W\}. Given a convex bipartite graph G in the compact form Dekel and Sahni designed an O(l og(2)(n))-time, n-processor EREW PRAM algorithm to compute a maximum m atching in G, We show that the matching produced by their algorithm ca n be used to construct optimally in parallel a maximum set of independ ent vertices. Our algorithm runs in O(log n) time with nl log n proces sors on an Arbitrary CRCW PRAM.