Matching is as easy as matrix inversion

Ketan Mulmuley; Umesh Vazirani; Vijay V. Vazirani

doi:10.1145/28395.383347

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.

Keywords

Inversion (geology)CitationComputer scienceMatching (statistics)Matrix (chemical analysis)Library scienceInformation retrievalMathematicsGeology

Affiliated Institutions

Related Publications

Partitioning Sparse Matrices with Eigenvectors of Graphs

Alex Pothen , Horst D. Simon , K. N. Liou

The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An ...

1990 SIAM Journal on Matrix Analysis and A... 1670 citations

Vector and parallel algorithms for the molecular dynamics simulation of macromolecules on shared‐memory computers

John E. Mertz , Douglas J. Tobias , Charles L. Brooks +1 more

Abstract A detailed description of vector/parallel algorithms for the molecular dynamics (MD) simulation of macromolecular systems on multiple processor, shared‐memory computers...

1991 Journal of Computational Chemistry 71 citations

Incremental, iterative data processing with timely dataflow

Derek G. Murray , Frank McSherry , Michael Isard +3 more

We describe the timely dataflow model for distributed computation and its implementation in the Naiad system. The model supports stateful iterative and incremental computations....

2016 Communications of the ACM 36 citations

On the Quality of Spectral Separators

Stephen Guattery , Gary L. Miller

Computing graph separators is an important step in many graph algorithms. A popular technique for finding separators involves spectral methods. However, there has not been much ...

1998 SIAM Journal on Matrix Analysis and A... 148 citations

Extensions of marginalized graph kernels

Pierre Mahé , Nobuhisa Ueda , Tatsuya Akutsu +2 more

Positive definite kernels between labeled graphs have recently been proposed. They enable the application of kernel methods, such as support vector machines, to the analysis and...

2004 186 citations

Publication Info

Year: 1987
Type: article
Pages: 345-354
Citations: 617
Access: Closed

External Links

Download PDF (Free) View on DOI.org Semantic Scholar

Social Impact

Altmetric

Matching is as easy as matrix inversion

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

617

OpenAlex

Influential

CrossRef

Cite This

APA Style

                            
                                    Ketan Mulmuley, 
                                
                                    Umesh Vazirani, 
                                
                                    Vijay V. Vazirani
                                
                            (1987). 
                            Matching is as easy as matrix inversion. 
                            Proceedings of the nineteenth annual ACM conference on Theory of computing  - STOC '87
                            
                            , 345-354.
                            https://doi.org/10.1145/28395.383347

Identifiers

DOI: 10.1145/28395.383347

Data Quality

Data completeness: 81%