Authors | A. Azad, A. Buluc, X. Li, X. Wang and J. Langguth |

Title | A Distributed-Memory Approximation Algorithm for Maximum Weight Perfect Bipartite Matching |

Afilliation | Scientific Computing |

Project(s) | Meeting Exascale Computing with Source-to-Source Compilers |

Status | Submitted |

Publication Type | Journal Article |

Year of Publication | 2018 |

Journal | SIAM Journal on Scientific Computing |

Publisher | SIAM |

Keywords | Bipartite graphs, graph theory, matching, parallel approximation algorithms, transversals |

Abstract | We design and implement an 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, such as those available in MC64, are widely used due to the lack of scalable alternatives. |

Citation Key | 25986 |