A dichotomy for bounded degree graph homomorphisms with nonnegative weights
From MaRDI portal
Publication:2678252
DOI10.1016/j.jcss.2022.09.002OpenAlexW3037882454MaRDI QIDQ2678252
Jin-Yi Cai, Artem Govorov, Martin Dyer
Publication date: 9 January 2023
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2002.02021
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing the partition function for graph homomorphisms
- A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
- The six and eight-vertex models revisited
- The complexity of partition functions
- Counting independent sets up to the tree threshold
- On Counting Independent Sets in Sparse Graphs
- Corrigendum: The complexity of counting graph homomorphisms
- On counting homomorphisms to directed acyclic graphs
- The Complexity of Enumeration and Reliability Problems
- Algorithms in Algebraic Number Theory
- Complexity Dichotomies for Counting Problems
- Algorithmic Pirogov-Sinai theory
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- Operations with structures
- Correlation Decay up to Uniqueness in Spin Systems
- Graph Homomorphisms with Complex Values: A Dichotomy Theorem