A permanent algorithm with exp[(n^1/3/2lnn)] expected speedup for 0-1 matrices

DOI10.1007/S00453-001-0072-0MaRDI QIDQ5956839zbMATH OpenOpenAlexFDO

Authors Eric Bax, Joel Franklin

Publication date 28 February 2002

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-001-0072-0

zbMATH Keywords

permanent algorithm

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• A mildly exponential approximation algorithm for the permanent
• Computing sparse permanents faster
• A Monte-Carlo Algorithm for Estimating the Permanent
• Computing the permanent of (some) complex matrices
• A hybrid algorithm for computing permanents of sparse matrices

Cited in

(11)

• Computing sparse permanents faster
• How fast can one compute the permanent of circulant matrices?
• Faster exponential-time algorithms in graphs of bounded average degree
• A hybrid algorithm for computing permanents of sparse matrices
• Computing the permanent modulo a prime power
• Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Counting perfect matchings as fast as Ryser
• Calculation of the permanent of a sparse positive matrix
• An efficient algorithm for computing permanental polynomials of graphs
• Counting short vector pairs by inner product and relations to the permanent

This page was built for publication: A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)]\) expected speedup for \(0-1\) matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5956839)