Artículos de revistas
Algorithms for Maximum Independent Set in Convex Bipartite Graphs
ALGORITHMICA, v.53, n.1, p.35-49, 2009
STEFANES, Marco A.
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. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.