Abstract
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|.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Booth, K., Lueker, G.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 335–379 (1976)
Bose, P., Chan, A., Dehne, F., Latzel, M.: Coarse grained parallel maximum matching in convex bipartite graphs. In: 13th International Parallel Processing Symposium (IPPS’99), pp. 125–129 (1999)
Caceres, E., Chan, A., Dehne, F., Prencipe, G.: Coarse grained parallel algorithms for detecting convex bipartite graphs. In: Proc. 26th Workshop on Graph-Theoretic Concepts in Computer Science (WG 2000), Konstanz, Germany (2000)
Chan, A., Dehne, F.: A note on coarse grained parallel integer sorting. Parallel Process. Lett. 9, 533–538 (1999)
Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms. McGraw–Hill, New York (1990)
Czumaj, A., Diks, K., Przytycka, T.: Parallel maximum independent set in convex bipartite graphs. Inf. Process. Lett. 59, 289–294 (1996)
Dehne, F., Fabri, A., Rau-Chaplin, A.: Scalable parallel geometric algorithms for coarse grained multicomputers. In: 9th Annual ACM Symposium on Computational Geometry, pp. 289–307 (1993)
Dekel, E., Sahni, S.: A parallel matching for convex bipartite graphs and applications to scheduling. J. Parallel Distrib. Comput. 1, 185–205 (1984)
Glover, F.: Maximum matching in a convex bipartite graph. Nav. Res. Logist. Q. 14, 313–316 (1967)
Goodrich, M.: Communication efficient parallel sorting. In: 28th Annual ACM Symposium on Theory of Computing (STOC’96), pp. 247–256 (1996)
Kuhn, H.: The Hungarian method for the assignment problem. Nav. Res. Logist. Q. 2, 83–97 (1955)
Lipski, W., Preparata, F.: Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Inform. 15, 329–346 (1981)
Steiner, G., Yeoman, J.: A linear time algorithm for maximum matchings in convex, bipartite graphs. Comput. Math. Appl. 31(12), 91–96 (1996)
Valiant, L.: A bridging model for parallel computation. Commun. ACM 33, 103–111 (1990)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by FAPESP (Proc. 98/06327-0). The first author was also supported by FAPESP (Proc. 96/04505–2), and CNPq/MCT/FINEP (PRONEX project 107/97).
Rights and permissions
About this article
Cite this article
Soares, J., Stefanes, M.A. Algorithms for Maximum Independent Set in Convex Bipartite Graphs. Algorithmica 53, 35–49 (2009). https://doi.org/10.1007/s00453-007-9006-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-007-9006-9