A Computational Proof of Complexity of Some Restricted Counting Problems

DOI10.1007/978-3-642-02017-9_17MaRDI QIDQ3630198zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Pinyan Lu, Mingji Xia

Publication date 3 June 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02017-9_17

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A computational proof of complexity of some restricted counting problems
• Computational complexity of Holant problems
• Computational complexity of counting problems on 3-regular planar graphs
• Holant problems and counting CSP
• Holant problems for regular graphs with complex edge functions

Cited in

(5)

• Computational complexity of counting problems on 3-regular planar graphs
• scientific article; zbMATH DE number 15994 (Why is no real title available?)
• A computational proof of complexity of some restricted counting problems
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• The complexity of symmetric Boolean parity Holant problems (extended abstract)

This page was built for publication: A Computational Proof of Complexity of Some Restricted Counting Problems

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