The polynomially bounded perfect matching problem Is in NC2

Agrawal, Manindra ; Hoang, Thanh Minh ; Thierauf, Thomas (2007) The polynomially bounded perfect matching problem Is in NC2 Lecture Notes in Computer Science, 4393 . pp. 489-499. ISSN 0302-9743

[img]
Preview
PDF - Author Version
179Kb

Official URL: http://www.springerlink.com/content/k3826356v37251...

Related URL: http://dx.doi.org/10.1007/978-3-540-70918-3_42

Abstract

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 NC2, and counting and enumerating all perfect matchings is in NC3. For general graphs with a polynomially bounded number of perfect matchings, they show both problems to be in NC3. 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 NC2. We extend the result to weighted graphs.

Item Type:Article
Source:Copyright of this article belongs to Springer.
ID Code:92030
Deposited On:26 May 2012 19:28
Last Modified:26 May 2012 19:28

Repository Staff Only: item control page