A Deterministic Parallel Algorithm for Bipartite Perfect Matching.
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 p...
| Publicado en: | Communications of the ACM Vol. 62; no. 3; pp. 109 - 116 |
|---|---|
| Autores principales: | , , |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Mar2019
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=134951016&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 134951016 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Mar2019 vid: 62 iid: 3 pid: 68 pub: Association for Computing Machinery artinfo: ui: 134951016 10.1145/3306208 ppf: 109 ppct: 7 formats: tig: atl: A Deterministic Parallel Algorithm for Bipartite Perfect Matching. aug: au: Fenner, Stephen Gurjar, Rohit Thierauf, Thomas affil: University of South Carolina, Columbia, SC, USA California Institute of Technology, Pasadena, CA, USA Aalen University, Germany su: Algorithms Bipartite graphs Computer science sug: subj: Algorithms Bipartite graphs Computer science ab: 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. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2019 holdings: @attributes: islocal: N |
|---|