Computing sparse permanents faster

DOI10.1016/J.IPL.2005.06.007MaRDI QIDQ1044712zbMATH OpenOpenAlexFDO

Authors Rocco A. Servedio, Andrew Wan

Publication date 18 December 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2005.06.007

zbMATH Keywords

algorithmscomputational complexitycombinatorial problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A hybrid algorithm for computing permanents of sparse matrices
• Computing the permanent of (some) complex matrices
• Computing the permanent modulo a prime power
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 3930346

Cites work

• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)]\) expected speedup for \(0-1\) matrices
• A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
• The complexity of computing the permanent

Cited in

(14)

• Random path method with pivoting for computing permanents of matrices
• Counting perfect matchings as fast as Ryser
• Below all subsets for some permutational counting problems
• Computing the permanent of (some) complex matrices
• Efficient computation of permanents, with applications to boson sampling and random matrices
• scientific article; zbMATH DE number 1577997 (Why is no real title available?)
• A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)]\) expected speedup for \(0-1\) matrices
• The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO
• Expressing polynomials as the permanent of low rank square matrices
• Computing permanents via determinants for some classes of sparse matrices
• A hybrid algorithm for computing permanents of sparse matrices
• Faster exponential-time algorithms in graphs of bounded average degree
• Calculation of the permanent of a sparse positive matrix
• Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors

This page was built for publication: Computing sparse permanents faster

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