Dichotomy result on 3-regular bipartite non-negative functions

DOI10.1016/j.tcs.2023.113745OpenAlexW4319025314MaRDI QIDQ5925621

Austen Z. Fan, Jin-Yi Cai

Publication date: 24 February 2023

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

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

zbMATH Keywords

bipartite graphdichotomy theoremHolant problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Holant problems for 3-regular graphs with complex edge functions
• Clustering to minimize the maximum intercluster distance
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• A Complete Dichotomy Rises from the Capture of Vanishing Signatures
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• Nonnegative Weighted #CSP: An Effective Complexity Dichotomy
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Holographic Algorithms
• The Complexity of Boolean Holant Problems with Nonnegative Weights
• Complexity Dichotomies for Counting Problems
• Complexity of Counting CSP with Complex Weights
• Holant Clones and the Approximability of Conservative Holant Problems
• Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms
• The complexity of the counting constraint satisfaction problem
• Dichotomy result on 3-regular bipartite non-negative functions

This page was built for publication: Dichotomy result on 3-regular bipartite non-negative functions