Matching is as easy as matrix inversion | Zendy

Ketan Mulmuley | Zendy; Umesh Vazirani | Zendy; Vijay V. Vazirani | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Matching is as easy as matrix inversion

Author(s) -

Ketan Mulmuley,

Umesh Vazirani,

Vijay V. Vazirani

Publication year - 1987

Publication title -

combinatorica

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 1.106

H-Index - 58

eISSN - 1439-6912

pISSN - 0209-9683

ISBN - 0-89791-221-7

DOI - 10.1007/bf02579206

Subject(s) - lemma (botany) , mathematics , inversion (geology) , computation , combinatorics , algorithm , matching (statistics) , graph , probabilistic logic , matrix (chemical analysis) , discrete mathematics , paleontology , statistics , materials science , structural basin , composite material , biology , ecology , poaceae

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research