Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, Abt. V
8514

01.12.2008

The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents is in NC
Dima Grigoriev and Marek Karpinski
[Download PostScript] [Download PDF]

It is shown that the problem of deciding and constructing a perfect matching in bipartite graphs G with the polynomial permanents of their n × n adjacency matrices A (perm(A) = nO(1)) are in the deterministic classes NC2 and NC3, respectively. We further design an NC3 algorithm for the problem of constructing all perfect matchings (enumeration problem) in a graph G with a permanent bounded by O(nk). The basic step was the development of a new symmetric function method for the decision algorithm and the new parallel technique for the matching enumerator problem. The enumerator algorithm works in O(log3n) parallel time and O(n3k+5.5 log n) processors. It entails among other things an efficient NC3-algorithm for computing small (polynomial bounded) arithmetic permanents and a sublinear parallel time algorithm for the bipartite matching with permanents up to 2nc.
Concerning the circuit complexity of the logical permanent (cf. [Ra 85]), we display a class of bounded permanent problems, each of superpolynomial monotone circuit complexity nΩ(log n)([Ra 85]), and which are computable within the uniform O(log2 n) depth and O(n4.5) size boolean circuits.

Last Change: 12/01/08 at 17:22:36
 English
Universität Bonn -> Institut für Informatik -> Abteilung V