Computational complexity of counting problems on 3-regular planar graphs
DOI10.1016/J.TCS.2007.05.023zbMATH Open1124.68083OpenAlexW2056017121MaRDI QIDQ2382289FDOQ2382289
Authors: Mingji Xia, Peng Zhang, Wen-Bo Zhao 
Publication date: 28 September 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.05.023
Recommendations
- The complexity of counting in sparse, regular, and planar graphs
- Theory and Applications of Models of Computation
- A computational proof of complexity of some restricted counting problems
- Holant problems for 3-regular graphs with complex edge functions
- A Computational Proof of Complexity of Some Restricted Counting Problems
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
- Statistical Mechanics of Dimers on a Plane Lattice
- Title not available (Why is that?)
- Dimer problem in statistical mechanics-an exact result
- Title not available (Why is that?)
- The Complexity of Enumeration and Reliability Problems
- The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
- Complexity of generalized satisfiability counting problems
- Some Results on Matchgates and Holographic Algorithms
- The complexity of counting in sparse, regular, and planar graphs
- Title not available (Why is that?)
- The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
- The Complexity of Planar Counting Problems
- Theory and Applications of Models of Computation
- Theory and Applications of Models of Computation
Cited In (29)
- Counting edge-injective homomorphisms and matchings on restricted graph classes
- Title not available (Why is that?)
- A graph polynomial for independent sets of bipartite graphs
- A computational proof of complexity of some restricted counting problems
- Satisfaction and power in unanimous majority influence decision models
- Faster exponential-time algorithms for approximately counting independent sets
- Counting problems in parameterized complexity
- A fixed-parameter perspective on \#BIS
- A fixed-parameter perspective on \#BIS
- Complexity of Ising polynomials
- Parameterized counting of partially injective homomorphisms
- Holographic algorithms with matchgates capture precisely tractable planar \#CSP
- Holographic algorithms by Fibonacci gates
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- Holographic algorithms on domains of general size
- 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
- Tensor network contractions for \#SAT
- Holographic algorithms: from art to science
- Spin systems on \(k\)-regular graphs with complex edge functions
- Some observations on holographic algorithms
- Counting polygon triangulations is hard
- A Computational Proof of Complexity of Some Restricted Counting Problems
- Theory and Applications of Models of Computation
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Holographic reduction, interpolation and hardness
- On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions
- The complexity of counting in sparse, regular, and planar graphs
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
This page was built for publication: Computational complexity of counting problems on 3-regular planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2382289)
