Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with perfect matching, maximum matching, NC:
TR09-091 | 23rd September 2009
Thanh Minh Hoang

On the Matching Problem for Special Graph Classes

Revisions: 1

In the present paper we show some new complexity bounds for
the matching problem for special graph classes.
We show that for graphs with a polynomially bounded number
of nice cycles, the decision perfect matching problem is in
$SPL$, it is hard for $FewL$, and the construction ... more >>>

TR17-059 | 6th April 2017
Ola Svensson, Jakub Tarnawski

The Matching Problem in General Graphs is in Quasi-NC

Revisions: 1

We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in $O(\log^3 n)$ time on $n^{O(\log^2 n)}$ processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the ... more >>>

ISSN 1433-8092 | Imprint