
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 19851989  Copyright 19851989 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) = 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 (enumeration problem) in a graph G with a permanent bounded by O(n^{k}). 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(log^{3}n) parallel time and O(n^{3k+5.5} log n) processors. It entails among other things an efficient NC^{3}algorithm for computing small (polynomial bounded) arithmetic permanents and a sublinear parallel time algorithm for the bipartite matching with permanents up to 2^{nc}. 

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