Abstract
Several schedule and assignment tasks can be modeled as a bipartite graph matching optimization, aiming to retrieve an optimal set of pairs connecting elements from two distinct sets. In this paper we investigate how to compute a weighted bipartite graph matching on Graphics Processing Units (GPUs) inspired by its low cost and increasing parallel processing power. We propose a data-parallel approach to be computed using GPUs processing kernels based on The Auction Algorithm, and data structures that allow it to be applied to problems modeled over complete bipartite graphs and also over huge bipartite graphs with connections across the neighborhood systems from two sets of 1D, 2D or 3D data grids.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bertsekas, D.P.: Auction algorithms for network flow problems: A tutorial introduction. Computational Optimization and Applications 1, 7–66 (1992)
Bertsekas, D.P., Castaon, D.A.: Parallel asynchronous hungarian methods for the assignment problem. ACM Trans. on Database Syst. 5, 212–230 (1993)
Cuda programming guide (2007), http://developer.download.nvidia.com/
Kuhn, H.W.: The hungarian method for the assignment problem. Naval Research Logistics Quarterly 2, 83–97 (1955)
Vasconcelos, C.N.: Bgm code, http://www.ic.uff.br/~crisnv/bgm/bgm.html
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
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vasconcelos, C.N., Rosenhahn, B. (2011). Bipartite Graph Matching on GPU over Complete or Local Grid Neighborhoods. In: Cabestany, J., Rojas, I., Joya, G. (eds) Advances in Computational Intelligence. IWANN 2011. Lecture Notes in Computer Science, vol 6691. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21501-8_53
Download citation
DOI: https://doi.org/10.1007/978-3-642-21501-8_53
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21500-1
Online ISBN: 978-3-642-21501-8
eBook Packages: Computer ScienceComputer Science (R0)