
University of Bonn > Department of Computer Science > Chair V  
CSReports 19851989  Copyright 19851989 University of Bonn, Department of Computer Science, Abt. V  
857

The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC
Dima Yu. Grigoriev, 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\times n$ adjacency matrices $A \;(perm(A)=n^{O(1)})$ are in the deterministic classes $NC^2$ and $NC^3$, respectively. We further design an $NC^3$ algorithm for the problem of constructing all perfect matchings ({\it enumeration problem}) in a graph $G$ with a permanent bounded by $O(n^k)$. The basic step was the development of a new symmetric functions method for the decision algorithm and the new parallel technique for the matching enumerator problem. The enumerator algorithm works in $O(\log^3 n)$ parallel time and $O(n^{3k+5.5}\cdot \log n)$ processors. In the case of arbitrary bipartite graphs it yields an timal' (up to the log $n$factor) parallel time algorithm for enumerating all the perfect matchings in a graph. It entails also among other things an efficient $NC^3$algorithm for computing small (polynomially bounded) arithmetic permanents, and a sublinear parallel time algorithm for enumerating all the perfect matchings in graphs with permanents up to $2^{n^\varepsilon}$. 

Last Change:
11/20/08 at 14:26:49
Deutsch 
University of Bonn > Department of Computer Science > Chair V 