Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4637553 | Applied Mathematics and Computation | 2006 | 9 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Heng Liang, Songqi Huang, Fengshan Bai,