Abstract
We design, implement, and evaluate GPU-based algorithms for the maximum cardinality matching problem in bipartite graphs. Such algorithms have a variety of applications in computer science, scientific computing, bioinformatics, and other areas. To the best of our knowledge, ours is the first study which focuses on the GPU implementation of the maximum cardinality matching algorithms. We compare the proposed algorithms with serial and multicore implementations from the literature on a large set of real-life problems where in majority of the cases one of our GPU-accelerated algorithms is demonstrated to be faster than both the sequential and multicore implementations.
Chapter PDF
Similar content being viewed by others
References
Azad, A., Halappanavar, M., Rajamanickam, S., Boman, E.G., Khan, A., Pothen, A.: Multithreaded algorithms for maximum matching in bipartite graphs. In: 26th IPDPS, pp. 860–872. IEEE (2012)
Azad, A., Pothen, A.: Multithreaded algorithms for matching in graphs with application to data analysis in flow cytometry. In: 26th IPDPS Workshops & PhD Forum, pp. 2494–2497. IEEE (2012)
Berge, C.: Two theorems in graph theory. P. Natl. Acad. Sci. USA 43, 842–844 (1957)
Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. SIAM, Philadelphia (2009)
Çatalyürek, Ü.V., Deveci, M., Kaya, K., Uçar, B.: Multithreaded clustering for multi-level hypergraph partitioning. In: 26th IPDPS, pp. 848–859. IEEE (2012)
Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM T. Math. Software 38(1) 1:1–1:25 (2011)
Duff, I.S., Erisman, A.M., Reid, J.K.: Direct Methods for Sparse Matrices. Oxford University Press, London (1986)
Duff, I.S., Kaya, K., Uçar, B.: Design, implementation, and analysis of maximum transversal algorithms. ACM T. Math. Software 38(2), 13 (2011)
Duff, I.S., Wiberg, T.: Remarks on implementation of O(n 1/2 τ) assignment algorithms. ACM T. Math. Software 14(3), 267–287 (1988)
Fagginger Auer, B.O., Bisseling, R.H.: A GPU algorithm for greedy graph matching. In: Keller, R., Kramer, D., Weiss, J.-P. (eds.) Facing Multicore-Challenge II. LNCS, vol. 7174, pp. 108–119. Springer, Heidelberg (2012)
Goldberg, A., Kennedy, R.: Global price updates help. SIAM J. Discrete Math. 10(4), 551–572 (1997)
Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum flow problem. J. Assoc. Comput. Mach. 35, 921–940 (1988)
Halappanavar, M., Feo, J., Villa, O., Tumeo, A., Pothen, A.: Approximate weighted matching on emerging manycore and multithreaded architectures. Int. J. High Perform. C. 26(4), 413–430 (2012)
Hochbaum, D.S.: The pseudoflow algorithm and the pseudoflow-based simplex for the maximum flow problem. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol. 1412, pp. 325–337. Springer, Heidelberg (1998)
Hopcroft, J.E., Karp, R.M.: An n 5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225–231 (1973)
John, P.E., Sachs, H., Zheng, M.: Kekulé patterns and Clar patterns in bipartite plane graphs. J. Chem. Inf. Comp. Sci. 35(6), 1019–1021 (1995)
Kaya, K., Langguth, J., Manne, F., Uçar, B.: Push-relabel based algorithms for the maximum transversal problem. Comput. Oper. Res. 40(5), 1266–1275 (2012)
Kim, W.Y., Kak, A.C.: 3-D object recognition using bipartite matching embedded in discrete relaxation. IEEE T. Pattern Anal. 13(3), 224–251 (1991)
Vasconcelos, C.N., Rosenhahn, B.: Bipartite graph matching computation on GPU. In: Cremers, D., Boykov, Y., Blake, A., Schmidt, F.R. (eds.) EMMCVPR 2009. LNCS, vol. 5681, pp. 42–55. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Deveci, M., Kaya, K., Uçar, B., Çatalyürek, Ü.V. (2013). GPU Accelerated Maximum Cardinality Matching Algorithms for Bipartite Graphs. In: Wolf, F., Mohr, B., an Mey, D. (eds) Euro-Par 2013 Parallel Processing. Euro-Par 2013. Lecture Notes in Computer Science, vol 8097. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40047-6_84
Download citation
DOI: https://doi.org/10.1007/978-3-642-40047-6_84
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40046-9
Online ISBN: 978-3-642-40047-6
eBook Packages: Computer ScienceComputer Science (R0)