Repository | Book | Chapter
On the permanent of certain circulant matrices
pp. 513-532
Abstract
The computation of the permanent of a matrix seems to be a very hard task, even for sparse (0, 1)-matrices. A number of results show that it is extremely unlikely that there is a polynomial time algorithm for computing the permanent. The best known algorithm is due to Ryser [22] and takes O(n 2n ) operations, where n is the matrix size.
Publication details
Published in:
Crapo Henry, Senato Domenico (2001) Algebraic combinatorics and computer science: a tribute to Gian-Carlo Rota. Dordrecht, Springer.
Pages: 513-532
DOI: 10.1007/978-88-470-2107-5_22
Full citation:
Codenotti B., Resta G. (2001) „On the permanent of certain circulant matrices“, In: H. Crapo & D. Senato (eds.), Algebraic combinatorics and computer science, Dordrecht, Springer, 513–532.