The Complexity of Planar Counting Problems

DOI10.1137/S0097539793304601MaRDI QIDQ4210088zbMATH OpenOpenAlexFDO

Authors V. Radhakrishnan, R. E. Stearns, H. 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

zbMATH Keywords

\(\text{D}^P\)-completegraphsNP-completeP-completeplanar

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The complexity of counting in sparse, regular, and planar graphs
• scientific article; zbMATH DE number 152108
• Complexity of generalized satisfiability counting problems

Cited in

(41)

• The complexity of power-index comparison
• The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
• Some observations on holographic algorithms
• The fewest clues problem
• On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions
• Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
• Counting polygon triangulations is hard
• Path puzzles: discrete tomography with a path constraint is hard
• Computational complexity of counting problems on 3-regular planar graphs
• Predecessor existence problems for finite discrete dynamical systems
• Computational aspects of mining maximal frequent patterns
• Counting dominating sets in some subclasses of bipartite graphs
• Rectangular spiral galaxies are still hard
• The complexity of counting in sparse, regular, and planar graphs
• On strongly planar not-all-equal 3SAT
• On strongly planar 3SAT
• scientific article; zbMATH DE number 4094812 (Why is no real title available?)
• Manipulating the quota in weighted voting games
• scientific article; zbMATH DE number 1948176 (Why is no real title available?)
• scientific article; zbMATH DE number 1500509 (Why is no real title available?)
• Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
• Complexity of counting feedback vertex sets
• Planar 3-SAT with a clause/variable cycle
• Counting dominating sets in generalized series-parallel graphs
• Planar 3-SAT with a clause/variable cycle
• ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS
• Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems
• On unique graph 3-colorability and parsimonious reductions in the plane
• Algorithms for four variants of the exact satisfiability problem
• The Complexity of Aggregates over Extractions by Regular Expressions
• On the complexity of generalized chromatic polynomials
• Hardness of pre-assignment problem for unique minimum vertex cover on planar graphs with maximum degree 3
• All paths lead to Rome
• Tetris with few piece types
• Counting independent sets in tree convex bipartite graphs
• Edge clique partition and cover beyond independence
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• The complexity of the Kth largest subset problem and related problems
• Errata for the paper ``Predecessor existence problems for finite discrete dynamical systems.
• Partition into cliques for cubic graphs: Planar case, complexity and approximation
• On symmetric signatures in holographic algorithms

This page was built for publication: The Complexity of Planar Counting Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210088)