Paper Info
Title
Bipartite Graph Matching Computation on GPU
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.
Year
DOI
Venue
2009
10.1007/978-3-642-03641-5_4
EMMCVPR
Keywords
Field
DocType
common node,fast result,bipartite graph matching,bipartite graph matching computation,distinct set,considered graph,end point,graphics hardware,graph theory,graphics processing units,bipartite graph matching problem,bipartite graph
Line graph,Computer science,Graph factorization,Folded cube graph,Bipartite graph,Matching (graph theory),Theoretical computer science,Factor-critical graph,3-dimensional matching,Blossom algorithm
Conference
Volume
ISSN
Citations 
5681
0302-9743
24
PageRank 
References 
Authors
2.06
8
2
Name
Order
Citations
PageRank
Cristina Nader Vasconcelos17612.15
Bodo Rosenhahn21733137.77