Paper Info
Title
Bipartite graph matching on GPU over complete or local grid neighborhoods
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.
Year
DOI
Venue
2011
10.1007/978-3-642-21501-8_53
IWANN (1)
Keywords
Field
DocType
data grid,gpus processing,huge bipartite graph,bipartite graph,local grid neighborhood,weighted bipartite graph,graphics processing units,parallel processing power,auction algorithm,data structure,complete bipartite graph
Adjacency matrix,Complete bipartite graph,Computer science,Folded cube graph,Bipartite graph,Matching (graph theory),Theoretical computer science,Assignment problem,3-dimensional matching,Blossom algorithm
Conference
Volume
ISSN
Citations 
6691
0302-9743
0
PageRank 
References 
Authors
0.34
3
2
Name
Order
Citations
PageRank
Cristina Nader Vasconcelos17612.15
Bodo Rosenhahn21733137.77