The Complexity of Enumeration and Reliability Problems
From MaRDI portal
Publication:3853129
Cited in
(only showing first 100 items - show all)- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- Universal relations and {\#}P-completeness
- On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
- Recognition and dualization of disguised bidual Horn functions.
- Counting and enumeration complexity with application to multicriteria scheduling
- On stability of a formal concept
- The complexity of weighted and unweighted \(\#\)CSP
- Consecutive-2 systems on trees
- Quorum systems constructed from combinatorial designs
- Unification algorithms cannot be combined in polynomial time.
- A study of symmetry breaking predicates and model counting
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- A Bayesian approach to relevance in game playing
- The Rank-One Quadratic Assignment Problem
- Not all FPRASs are equal: demystifying FPRASs for DNF-counting
- Rényi entropies as a measure of the complexity of counting problems
- Approximation to measurable functions and its relation to probabilistic computation
- A logic-based analysis of Dempster-Shafer theory
- The operators min and max on the polynomial hierarchy
- Decomposition representations of logical equations in problems of inversion of discrete functions
- The computational complexity of knot and matroid polynomials
- On the concentration of the number of solutions of random satisfiability formulas
- Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems
- Approximately counting approximately-shortest paths in directed acyclic graphs
- Learning to select branching rules in the DPLL procedure for satisfiability
- The complexity of estimating min-entropy
- Random partition models and complementary clustering of Anglo-Saxon place-names
- On computing minimal independent support and its applications to sampling and counting
- Towards fixed-parameter tractable algorithms for abstract argumentation
- A Dichotomy Theorem for Polynomial Evaluation
- Search for all \(d\)-mincuts of a limited-flow network
- Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph
- Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
- Two-path subsets: Efficient counting and applications to performability analysis
- SELF-SPECIFYING MACHINES
- Querying disjunctive databases through nonmonotonic logics
- Counting near-perfect matchings on \(C_m \times C_n\) tori of odd order in the Maple system
- Counting minimal unsatisfiable subsets
- Predecessor existence problems for finite discrete dynamical systems
- The complexity of solution-free sets of integers for general linear equations
- Hard Enumeration Problems in Geometry and Combinatorics
- New upper bound for the \#3-SAT problem
- On the dimer problem of the vertex-edge graph of a cubic graph
- Some observations on the connection between counting and recursion
- Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
- The maximum clique problem
- Heuristic enhancements of the search for the generation of all perfect matchings
- The complexity of computing the permanent
- Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
- scientific article; zbMATH DE number 7561410 (Why is no real title available?)
- The computational complexity of maximization and integration
- Counting trees in a graph is \(\# \text{P}\)-complete
- Algorithms to count paths and cycles
- Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#\(P\)-complete
- The effect of combination functions on the complexity of relational Bayesian networks
- On the number of perfect matchings in the line graph of a traceable graph
- Classical simulation of quantum circuits by half Gauss sums
- Proper colorability of segment intersection graphs
- Approximately counting paths and cycles in a graph
- On the usefulness of linear modular arithmetic in constraint programming
- Lifted algorithms for symmetric weighted first-order model sampling
- Counting the number of vertex covers in a trapezoid graph
- Combinatorial properties of Farey graphs
- Rumor correction maximization problem in social networks
- A very hard log-space counting class
- Polynomial-time algorithms for multimarginal optimal transport problems with structure
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- Counting dominating sets in generalized series-parallel graphs
- Algorithmic uses of the Feferman-Vaught theorem
- On sampling simple paths in planar graphs according to their lengths
- Polynomial time algorithm for an optimal stable assignment with multiple partners
- Voronoi diagrams with barriers and on polyhedra for minimal path planning
- The Computational Complexity of the Tutte Plane: the Bipartite Case
- Tractable counting of the answers to conjunctive queries
- Phase transition of multivariate polynomial systems
- Counting over non-planar graphs
- Sparse reliable graph backbones
- Enumerative counting is hard
- On listing, sampling, and counting the chordal graphs with edge constraints
- Computational complexity of impact size estimation for spreading processes on networks
- Computational complexity of three-dimensional discrete tomography with missing data
- A note on observables for counting trails and paths in graphs
- Lower bounds and the hardness of counting properties
- Weak minimization of DFA -- an algorithm and applications
- Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model
- The computational complexity of QoS measures for orchestrations. The computational complexity of QoS measures
- Counting Unlabelled Subtrees of a Tree is #P-complete
- An extended knowledge compilation map for conditional preference statements-based and generalized additive utilities-based languages
- On the number of go positions on lattice graphs
- The complexity of weighted Boolean \#CSP with mixed signs
- Tally NP sets and easy census functions.
- The complexity of counting locally maximal satisfying assignments of Boolean CSPs
- Lee-Yang theorems and the complexity of computing averages
- Counting consistent phylogenetic trees is \#P-complete
- scientific article; zbMATH DE number 7300350 (Why is no real title available?)
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- The fewest clues problem
- On the Complexity of Holant Problems
- Optimal testing for planted satisfiability problems
This page was built for publication: The Complexity of Enumeration and Reliability Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3853129)
