Paper Info
Title
A Parallel Tree Grafting Algorithm for Maximum Cardinality Matching in Bipartite Graphs
Abstract
In computing matching's in graphs on parallel processors, it is challenging to achieve high performance because these algorithms rely on searching for paths in the graph, and when these paths become long, there is little concurrency. We present a new algorithm and its shared-memory parallelization for computing maximum cardinality matching's in bipartite graphs. Our algorithm searches for augmenting paths via specialized breadth-first searches (BFS) from multiple source vertices, hence creating more parallelism than single source algorithms. Unfortunately, algorithms that employ multiple-source searches cannot discard a search tree once no augmenting path is discovered from the tree, unlike algorithms that rely on single-source searches. We describe a novel tree-grafting method that eliminates most of the redundant edge traversals resulting from this property of multiple-source searches. We also employ the recent direction-optimizing BFS algorithm as a subroutine to discover augmenting paths faster. Our algorithm compares favourably with the current best algorithms in terms of the number of edges traversed, the average augmenting path length, and the number of iterations. We provide a proof of correctness for our algorithm. Our NUMA-aware implementation is scalable to 80 threads of an Intel multiprocessor. On average, our parallel algorithm runs an order of magnitude faster than the fastest algorithms available. The performance improvement is more significant on graphs with small matching number.
Year
DOI
Venue
2015
10.1109/IPDPS.2015.68
International Parallel & Distributed Processing Symposium
Field
DocType
ISSN
Factor graph,Parallel algorithm,Computer science,Parallel computing,Breadth-first search,Bipartite graph,Algorithm,Matching (graph theory),Hopcroft–Karp algorithm,3-dimensional matching,Blossom algorithm,Distributed computing
Conference
1530-2075
Citations 
PageRank 
References 
4
0.41
13
Authors
3
Name
Order
Citations
PageRank
Ariful Azad113815.71
Aydin Buluc2105767.49
Alex Pothen3212.46