The complexity of counting in sparse, regular, and planar graphs
From MaRDI portal
Recommendations
Cited in
(97)- Sampling Eulerian orientations of triangular lattice graphs
- On counting 3-D matchings of size \(k\)
- The complexity of counting homeomorphs
- Counting trees in a graph is \(\# \text{P}\)-complete
- The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
- Some observations on holographic algorithms
- On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions
- The complexity of Bayesian networks specified by propositional and relational languages
- Counting minimal transversals of -acyclic hypergraphs
- Counting independent sets in cocomparability graphs
- Counting models for 2SAT and 3SAT formulae
- Holographic reduction, interpolation and hardness
- Holographic algorithms by Fibonacci gates
- Holographic reduction for some counting problems
- Parameterized counting of partially injective homomorphisms
- Counting subset repairs with functional dependencies
- Counting polygon triangulations is hard
- The complexity of counting edge colorings for simple graphs
- Dichotomy results for fixed point counting in Boolean dynamical systems
- A fixed-parameter perspective on \#BIS
- Counting edge-injective homomorphisms and matchings on restricted graph classes
- On the spectrum and number of convex sets in graphs
- Expected computations on color spanning sets
- 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
- Using binary patterns for counting falsifying assignments of conjunctive forms
- Minimal autocatalytic networks
- A complete dichotomy rises from the capture of vanishing signatures
- Counting Maximal Independent Sets in Subcubic Graphs
- A graph polynomial for independent sets of bipartite graphs
- Circuit complexity of properties of graphs with constant planar cutwidth
- Sequential Monte Carlo for counting vertex covers in general graphs
- Approximately counting locally-optimal structures
- Counting minimal dominating sets
- Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
- Counting independent sets in claw-free graphs
- Holant problems for 3-regular graphs with complex edge functions
- Approximately Counting Locally-Optimal Structures
- Model counting of monotone conjunctive normal form formulas with spectra
- Proof systems and transformation games
- FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES
- On planar Toeplitz graphs
- Closest pair and the post office problem for stochastic points
- Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions
- The complexity of complex weighted Boolean \#CSP
- The complexity of generalized domino tilings
- Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
- The Complexity of Planar Counting Problems
- An exact exponential time algorithm for counting bipartite cliques
- Counting matchings with k unmatched vertices in planar graphs
- A graph theoretic approach to solve special knapsack problems in polynomial time
- scientific article; zbMATH DE number 1834679 (Why is no real title available?)
- Computing cooperative solution concepts in coalitional skill games
- Counting problems in parameterized complexity
- Spectral independence in high-dimensional expanders and applications to the hardcore model
- On the counting complexity of mathematical nanosciences
- The Complexity of Approximately Counting Retractions to Square-free Graphs
- A Method for Computing the Merrifield–Simmons Index on Benzenoid Systems
- scientific article; zbMATH DE number 7559233 (Why is no real title available?)
- Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
- Counting shortest two disjoint paths in cubic planar graphs with an NC algorithm
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
- Planar 3-SAT with a clause/variable cycle
- Hardness of identity testing for restricted Boltzmann machines and Potts models
- Stochastic enumeration method for counting trees
- Classification of a Class of Counting Problems Using Holographic Reductions
- A computational proof of complexity of some restricted counting problems
- ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS
- Holographic algorithms with matchgates capture precisely tractable planar \#CSP
- Theory and Applications of Models of Computation
- Maximum box problem on stochastic points
- Dichotomy result on 3-regular bipartite non-negative functions
- Bipartite 3-regular counting problems with mixed signs
- Dichotomy result on 3-regular bipartite non-negative functions
- Bipartite 3-regular counting problems with mixed signs
- Algorithms for four variants of the exact satisfiability problem
- Counting independent sets in graphs with bounded bipartite pathwidth
- Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial
- Holographic algorithms: from art to science
- Edge flipping in graphs
- Cutting Barnette graphs perfectly is hard
- Exponential time complexity of the complex weighted Boolean \#CSP
- Computational complexity of counting coincidences
- Anytime approximate formal feature attribution
- Sub-exponential time lower bounds for \#VC and \#Matching on 3-regular graphs
- Spin systems on k-regular graphs with complex edge functions
- The Pareto cover problem
- The complexity of pre-assignment problem for unique minimum vertex cover on bipartite graphs
- Easier ways to prove counting hard: a dichotomy for generalized \#SAT, applied to constraint graphs
- Counting independent sets in tree convex bipartite graphs
- Fibonacci numbers of generalized Fibonacci graphs
- Counting and enumerating independent sets with applications to combinatorial optimization problems
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Fair cost allocations under conflicts - a game-theoretic point of view -
- Counting the number of independent sets in chordal graphs
- Exact algorithms for exact satisfiability and number of perfect matchings
This page was built for publication: The complexity of counting in sparse, regular, and planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2784460)
