A hybrid algorithm for computing permanents of sparse matrices

摘要

The permanent of matrices has wide applications in many fields of science and engineering. It is, however, a #P-complete problem in counting. The best-known algorithm for computing the permanent, which is due to Ryser [Combinatorial Mathematics, The Carus Mathematical Monographs, vol. 14, Mathematical Association of America, Washington, DC, 1963], runs O(n2n−1) in time. It is possible to speed up algorithms for matrices with special structures, which arise commonly in applications. Most algorithms discussed before focus on 0, 1 matrix. In this paper, a hybrid algorithm is proposed. It is efficient for sparse matrices.