The matching problem for bipartite graphs with polynomially bounded permanents is in NC
- 1 October 1987
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 166-172
- https://doi.org/10.1109/sfcs.1987.56
Abstract
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 functions method for the decision algorithm and the new parallel technique for the matching enumerator problem. The enumerator algorithm works in O(log3 n) parallel time and O(n3k+5.5 · log n) processors. In the case of arbitrary bipartite graphs it yields an 'optimal' (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 NC3-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 2nε.Keywords
This publication has 22 references indexed in Scilit:
- A las vegas rnc algorithm for maximum matchingCombinatorica, 1986
- Decomposition by clique separatorsDiscrete Mathematics, 1985
- Pseudorandom number generation and space complexityInformation and Control, 1985
- NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matchingPublished by Springer Nature ,1985
- A taxonomy of problems with fast parallel algorithmsInformation and Control, 1985
- Computing Rational Zeros of Integral Polynomials by p-Adic ExpansionSIAM Journal on Computing, 1983
- Characterizations of strongly chordal graphsDiscrete Mathematics, 1983
- The complexity of computing the permanentTheoretical Computer Science, 1979
- Permanents of 0,1-matricesJournal of Combinatorial Theory, Series A, 1974
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973