Algorithms for Maximum Independent Set in Convex Bipartite Graphs

dc.creatorSOARES, Jose
dc.creatorSTEFANES, Marco A.
dc.date.accessioned2012-10-20T04:42:45Z
dc.date.accessioned2018-07-04T15:45:52Z
dc.date.available2012-10-20T04:42:45Z
dc.date.available2018-07-04T15:45:52Z
dc.date.created2012-10-20T04:42:45Z
dc.date.issued2009
dc.identifierALGORITHMICA, v.53, n.1, p.35-49, 2009
dc.identifier0178-4617
dc.identifierhttp://producao.usp.br/handle/BDPI/30399
dc.identifier10.1007/s00453-007-9006-9
dc.identifierhttp://dx.doi.org/10.1007/s00453-007-9006-9
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1627038
dc.description.abstractA 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|.
dc.languageeng
dc.publisherSPRINGER
dc.relationAlgorithmica
dc.rightsCopyright SPRINGER
dc.rightsrestrictedAccess
dc.subjectConvex bipartite graphs
dc.subjectIndependent sets
dc.subjectBSP/CGM algorithms
dc.subjectParallel algorithm
dc.titleAlgorithms for Maximum Independent Set in Convex Bipartite Graphs
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución