Abstract
This paper outlines a permanent algorithm with mildly exponential expected speedup over Ryser's inclusion and exclusion algorithm for 0-1 matrices. The algorithm is based on a finite-difference formula that is a generalization of Ryser's formula. The matrix is augmented by a column of entries selected to produce zero-valued terms in the formula. The algorithm achieves speedup by avoiding computation of many zero-valued terms.
Similar content being viewed by others
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bax, Franklin A Permanent Algorithm with exp[Ω (n ^{1/3}/2 ln n )] Expected Speedup for 0-1 Matrices . Algorithmica 32, 157–162 (2002). https://doi.org/10.1007/s00453-001-0072-0
Issue Date:
DOI: https://doi.org/10.1007/s00453-001-0072-0