Bipartite graph matching computation on GPU
- authored by
- Cristina Nader Vasconcelos, Bodo Rosenhahn
- Abstract
The Bipartite Graph Matching Problem is a well studied topic in Graph Theory. Such matching relates pairs of nodes from two distinct sets by selecting a subset of the graph edges connecting them. Each edge selected has no common node as its end points to any other edge within the subset. When the considered graph has huge sets of nodes and edges the sequential approaches are impractical, specially for applications demanding fast results. In this paper we investigate how to compute such matching on Graphics Processing Units (GPUs) motivated by its increasing processing power made available with decreasing costs. We present a new data-parallel approach for computing bipartite graph matching that is efficiently computed on today's graphics hardware and apply it to solve the correspondence between 3D samples taken over a time interval.
- Organisation(s)
-
Institute of Information Processing
- External Organisation(s)
-
Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio)
- Type
- Conference contribution
- Pages
- 42-55
- No. of pages
- 14
- Publication date
- 2009
- Publication status
- Published
- Peer reviewed
- Yes
- ASJC Scopus subject areas
- Theoretical Computer Science, Computer Science(all)
- Electronic version(s)
-
https://doi.org/10.1007/978-3-642-03641-5_4 (Access:
Unknown)
