AuthorsJ. Langguth, A. Azad, A. Buluc, X. Li and X. Wang
TitleA distributed - memory parallel approximation of maximum weight perfect bipartite matching
AfilliationScientific Computing
Project(s)UMOD: Understanding and Monitoring Digital Wildfires
Publication TypeTalks, contributed
Year of Publication2018
Location of TalkSparse Days 2018, Toulouse, France
KeywordsBipartite graphs, graph theory, matching, parallel approximation algorithms, transversals

We discuss efficient parallel approximation algorithm for the problem of maximum weight perfect matching in bipartite graphs, i.e. the problem of finding a set of non-adjacent edges that covers all vertices and has maximum
weight. This problem differs from the maximum weight matching problem, for which scalable approximation algorithms are known. It is primarily motivated by finding good pivots in scalable sparse direct solvers before
factorization where sequential implementations of maximum weight perfect matching algorithms, are generally used due to the lack of scalable alternatives. To overcome this limitation, we propose a parallel distributed memory
algorithm and discuss its approximation properties.


Similar talk was given again at Inria Bordeaux in October 2018

Citation Key26133

Contact person