Counting perfect matchings as fast as Ryser
Författare
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.
Avdelning/ar
Publiceringsår
2012
Språk
Engelska
Sidor
914-921
Publikation/Tidskrift/Serie
[Host publication title missing]
Länkar
Dokumenttyp
Konferensbidrag
Förlag
Society for Industrial and Applied Mathematics
Ämne
- Computer Science
Conference name
ACM-SIAM Symposium on Discrete Algorithms
Conference date
2012-01-17 - 2012-01-19
Conference place
Kyoto, Japan
Status
Published
Projekt
- Exact algorithms
Forskningsgrupp
- Algorithms