The Complexity of Planar Counting Problems
From MaRDI portal
Publication:4210088
DOI10.1137/S0097539793304601zbMath0911.68060OpenAlexW1975501803MaRDI QIDQ4210088
Richard E. Stearns, Venkatesh Radhakrishnan, Harry B. III Hunt, Madhav V. Marathe
Publication date: 20 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539793304601
Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Some observations on holographic algorithms, The fewest clues problem, Computational complexity of counting problems on 3-regular planar graphs, On unique graph 3-colorability and parsimonious reductions in the plane, Algorithms for four variants of the exact satisfiability problem, Towards a dichotomy theorem for the counting constraint satisfaction problem, Counting dominating sets in some subclasses of bipartite graphs, Rectangular spiral galaxies are still hard, The complexity of the \(K\)th largest subset problem and related problems, The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes., The Complexity of Aggregates over Extractions by Regular Expressions, Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible, Manipulating the quota in weighted voting games, On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions, Errata for the paper ``Predecessor existence problems for finite discrete dynamical systems., Predecessor existence problems for finite discrete dynamical systems, Partition into cliques for cubic graphs: Planar case, complexity and approximation, On the complexity of generalized chromatic polynomials, On symmetric signatures in holographic algorithms, Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems, Unnamed Item, Computational aspects of mining maximal frequent patterns, Counting independent sets in tree convex bipartite graphs, The complexity of power-index comparison, Counting dominating sets in generalized series-parallel graphs, Path puzzles: discrete tomography with a path constraint is hard, ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS, Planar 3-SAT with a clause/variable cycle, Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
