Computing sparse permanents faster

DOI10.1016/J.IPL.2005.06.007zbMath1184.68625OpenAlexW2160392814MaRDI QIDQ1044712

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (3)

Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors ⋮ Unnamed Item ⋮ Faster exponential-time algorithms in graphs of bounded average degree

Cites Work

• Unnamed Item
• The complexity of computing the permanent
• A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
• A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)\) expected speedup for \(0-1\) matrices]

This page was built for publication: Computing sparse permanents faster