A deterministic parallel algorithm for bipartite perfect matching
| Autor: | Stephen A. Fenner, Thomas Thierauf, Rohit Gurjar |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Lemma (mathematics)
General Computer Science Matching (graph theory) Computer science Parallel algorithm Minimum weight 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Construct (python library) 01 natural sciences Randomized algorithm Combinatorics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Bipartite graph Isolation (database systems) Randomness |
| Zdroj: | Communications of the ACM. 62:109-115 |
| ISSN: | 1557-7317 0001-0782 |
| DOI: | 10.1145/3306208 |
| Popis: | A fundamental quest in the theory of computing is to understand the power of randomness. It is not known whether every problem with an efficient randomized algorithm also has one that does not use randomness. One of the extensively studied problems under this theme is that of perfect matching. The perfect matching problem has a randomized parallel (NC) algorithm based on the Isolation Lemma of Mulmuley, Vazirani, and Vazirani. It is a long-standing open question whether this algorithm can be derandomized. In this article, we give an almost complete derandomization of the Isolation Lemma for perfect matchings in bipartite graphs. This gives us a deterministic parallel (quasi-NC) algorithm for the bipartite perfect matching problem. Derandomization of the Isolation Lemma means that we deterministically construct a weight assignment so that the minimum weight perfect matching is unique. We present three different ways of doing this construction with a common main idea. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|