Computational complexity of counting problems on 3-regular planar graphs
type: Item
instance of: scholarly article
title: Computational complexity of counting problems on 3-regular planar graphs
zbMATH Open document ID: 1124.68083
author: Mingji Xia
author: Peng Zhang
author: Wen-Bo Zhao
published in: Theoretical Computer Science
publication date: 2007-09-28T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5196814
zbMATH Keywords: {\#}P-completeness
zbMATH Keywords: holographic reduction
zbMATH Keywords: vertex cover
zbMATH Keywords: matching
MaRDI profile type: Publication
full work available at URL: j.tcs.2007.05.023
OpenAlex ID: W2056017121
cites work: Q5501802
cites work: Some Results on Matchgates and Holographic Algorithms
cites work: Theory and Applications of Models of Computation
cites work: Complexity of generalized satisfiability counting problems
cites work: Statistical Mechanics of Dimers on a Plane Lattice
cites work: The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
cites work: The Complexity of Planar Counting Problems
cites work: The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
cites work: Q5605168
cites work: The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
cites work: Q4298260
cites work: Dimer problem in statistical mechanics-an exact result
cites work: The complexity of counting in sparse, regular, and planar graphs
cites work: The Complexity of Enumeration and Reliability Problems
DOI: 10.1016/J.TCS.2007.05.023
description: scientific article