Artículos de revistas
Algorithms for Maximum Independent Set in Convex Bipartite Graphs
Fecha
2009Registro en:
ALGORITHMICA, v.53, n.1, p.35-49, 2009
0178-4617
10.1007/s00453-007-9006-9
Autor
SOARES, Jose
STEFANES, Marco A.
Institución
Resumen
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|.