[PDF][PDF] Matching is as easy as matrix inversion
K Mulmuley, UV Vazirani, VV Vazirani - Proceedings of the nineteenth …, 1987 - dl.acm.org
K Mulmuley, UV Vazirani, VV Vazirani
Proceedings of the nineteenth annual ACM symposium on Theory of computing, 1987•dl.acm.orgA new algorithm for finding a maximum matching in a general graph is presented; its special
feature being that the only computationally non-trivial step required in its execution is the
inversion of a single integer matrix. Since this step can be parallelized, we get a simple
parallel (RNC2) algorithm. At the heart of our algorithm lies a probabilistic lemma, the
isolating lemma. We show applications of this lemma to parallel computation and
randomized reductions.
feature being that the only computationally non-trivial step required in its execution is the
inversion of a single integer matrix. Since this step can be parallelized, we get a simple
parallel (RNC2) algorithm. At the heart of our algorithm lies a probabilistic lemma, the
isolating lemma. We show applications of this lemma to parallel computation and
randomized reductions.
Abstract
A new algorithm for finding a maximum matching in a general graph is presented; its special feature being that the only computationally non-trivial step required in its execution is the inversion of a single integer matrix. Since this step can be parallelized, we get a simple parallel (RNC2) algorithm. At the heart of our algorithm lies a probabilistic lemma, the isolating lemma. We show applications of this lemma to parallel computation and randomized reductions.
ACM Digital Library