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 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  English Universität Bonn -> Institut für Informatik -> Abteilung V