Partition functions on k-regular graphs with \0,1\-vertex assignments and real edge functions

DOI10.1016/J.TCS.2012.12.043MaRDI QIDQ391089zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Michael Kowalczyk

Publication date 10 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.12.043

zbMATH Keywords

counting complexitydichotomy theoremHolant problemholographic algorithmpartition function

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions
• Spin systems on k-regular graphs with complex edge functions
• Spin systems on graphs with complex edge functions and specified degree regularities
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Holant problems for regular graphs with complex edge functions

Cites work

• A Complexity Dichotomy for Partition Functions with Mixed Signs
• A computational proof of complexity of some restricted counting problems
• A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions
• Computational complexity of counting problems on 3-regular planar graphs
• Holant problems and counting CSP
• Holant problems for regular graphs with complex edge functions
• Holographic algorithms: from art to science
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• On counting homomorphisms to directed acyclic graphs
• On the complexity of H-coloring
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• The complexity of computing the permanent
• The complexity of counting in sparse, regular, and planar graphs
• The Complexity of Enumeration and Reliability Problems
• The complexity of partition functions

Cited in

(12)

• Mixed partition functions and exponentially bounded edge-connection rank
• A complete dichotomy rises from the capture of vanishing signatures
• Gadgets and anti-gadgets leading to a complexity dichotomy
• Spin systems on graphs with complex edge functions and specified degree regularities
• Holant problems for regular graphs with complex edge functions
• Holant problems for 3-regular graphs with complex edge functions
• A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions
• On the Complexity of Holant Problems
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Theory and Applications of Models of Computation
• Dichotomy result on 3-regular bipartite non-negative functions
• Spin systems on k-regular graphs with complex edge functions

This page was built for publication: Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions

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