Counting perfect matchings as fast as Ryser
Author
Summary, in English
We also give a simple argument why the general exact set cover counting problem over a slightly superpolynomial sized family of subsets of an n element ground set cannot be solved in O*(2(1−ε1)n) time for any ε1 > 0 unless there are O*(2(1−ε2)n) time algorithms for computing an n x n 0/1 matrix permanent, for some ε2 > 0 depending only on ε1.
Department/s
Publishing year
2012
Language
English
Pages
914-921
Publication/Series
[Host publication title missing]
Links
Document type
Conference paper
Publisher
Society for Industrial and Applied Mathematics
Topic
- Computer Science
Conference name
ACM-SIAM Symposium on Discrete Algorithms
Conference date
2012-01-17 - 2012-01-19
Conference place
Kyoto, Japan
Status
Published
Project
- Exact algorithms
Research group
- Algorithms