Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
The Polynomially Bounded Perfect Matching Problem Is in NC 2
verfasst von : Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf
Erschienen in: STACS 2007
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The
perfect matching problem
is known to be in
P
, in randomized
NC
, and it is hard for
NL
. Whether the perfect matching problem is in
NC
is one of the most prominent open questions in complexity theory regarding parallel computations.
Grigoriev and Karpinski [GK87] studied the perfect matching problem for bipartite graphs with polynomially bounded permanent. They showed that for such bipartite graphs the problem of deciding the existence of a perfect matchings is in
NC
2
, and counting and enumerating all perfect matchings is in
NC
3
. For general graphs with a polynomially bounded number of perfect matchings, they show both problems to be in
NC
3
.
In this paper we extend and improve these results. We show that for any graph that has a polynomially bounded number of perfect matchings, we can construct all perfect matchings in
NC
2
. We extend the result to weighted graphs.