A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions

DOI10.1007/978-3-642-13562-0_30MaRDI QIDQ3569087zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Michael Kowalczyk

Publication date 17 June 2010

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-13562-0_30

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
• A Cauchy-Davenport type result for arbitrary regular graphs
• On a class of edge-regular graphs
• On (I*.n)-regular graphs
• scientific article; zbMATH DE number 4047778
• On \((r, 2, (r - 1)(r - 1))\)-regular graphs
• Integral graphs and \((k,\tau )\)-regular sets
• On existence and regularity of graphs with certain properties
• On distance-regular graphs with \(k_ i=k_ j\)
• Characterization of a class of edge-regular graphs

Cited in

(10)

• Holographic reduction, interpolation and hardness
• Lee-Yang theorems and the complexity of computing averages
• A dichotomy for real weighted Holant problems
• Spin systems on graphs with complex edge functions and specified degree regularities
• Holant problems for regular graphs with complex edge functions
• The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
• Holant problems for 3-regular graphs with complex edge functions
• Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
• 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: A Dichotomy for 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 Q3569087)