The Complexity of Enumeration and Reliability Problems

DOI10.1137/0208032zbMATH Open0419.68082DBLPjournals/siamcomp/Valiant79OpenAlexW2115826669WikidataQ55878545 ScholiaQ55878545MaRDI QIDQ3853129FDOQ3853129

Authors: Leslie G. Valiant 

Publication date: 1979

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/ed9b4ff3d634a448747b7d51f56abc81ef9d0054

zbMATH Keywords

computational complexityenumerationcounting problemsprobabilistic networkcompleteness resultscounting maximal cliquescounting perfect matchings in bipartite graphscounting trees in a connected graph

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Connectivity (05C40) Applications of graph theory to circuits and networks (94C15) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (only showing first 100 items - show all)

• The complexity of weighted and unweighted \(\#\)CSP
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• The computational complexity of knot and matroid polynomials
• Learning to select branching rules in the DPLL procedure for satisfiability
• Decomposition representations of logical equations in problems of inversion of discrete functions
• Search for all \(d\)-mincuts of a limited-flow network
• Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
• Hard Enumeration Problems in Geometry and Combinatorics
• Predecessor existence problems for finite discrete dynamical systems
• New upper bound for the \#3-SAT problem
• Counting trees in a graph is \(\# \text{P}\)-complete
• Algorithms to count paths and cycles
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• Algorithmic uses of the Feferman-Vaught theorem
• Enumerative counting is hard
• Counting Unlabelled Subtrees of a Tree is #P-complete
• Sparse reliable graph backbones
• Lee-Yang theorems and the complexity of computing averages
• A survey of some network reliability analysis and synthesis results
• Bicycle dimension and special points of the Tutte polynomial
• Counting almost minimum cutsets with reliability applications
• On the parameterized complexity of approximate counting
• Algorithms for four variants of the exact satisfiability problem
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• Probabilistic query answering over inconsistent databases
• The complexity of computing maximal word functions
• The consequences of eliminating NP solutions
• Enumerating Hamiltonian cycles
• On some natural complete operators
• Simple characterizations of \(P(\# P)\) and complete problems
• Optimal inter-object correlation when replicating for availability
• Residual reliability of P-threshold graphs
• Counting the number of solutions for instances of satisfiability
• On counting problems and the polynomial-time hierarchy
• Counting problems and ranks of matrices
• A new lower bound for the number of perfect matchings of line graph
• A polynomial-time algorithm for computing \(K\)-terminal residual reliability of \(d\)-trapezoid graphs
• Counting independent sets in a tolerance graph
• Model checking in the modal \(\mu \)-calculus and generic solutions
• On the construction of parallel computers from various basis of Boolean functions
• The computational complexity of abduction
• Counting and Gröbner bases
• Model counting meets \(F_0\) estimation
• Computing residual connectedness reliability for restricted networks
• The parameterized complexity of probability amplification
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• On the complexity of partially observed Markov decision processes
• Fast and simple algorithms to count the number of vertex covers in an interval graph
• Counting solutions to binomial complete intersections
• An application of the planar separator theorem to counting problems
• Reliability of task graph schedules with transient and fail-stop failures: complexity and algorithms
• Classifying the computational complexity of problems
• Nonerasing, counting, and majority over the linear time hierarchy
• Complexity of Counting the Optimal Solutions
• The complexity of the characteristic and the minimal polynomial.
• Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms
• Dichotomy results for fixed point counting in Boolean dynamical systems
• Enumeration aspects of maximal cliques and bicliques
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• Computing optimal assignments for residual network reliability
• Mathematical aspects of concept analysis
• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
• A complexity theory for feasible closure properties
• Robust planning with incomplete domain models
• On the complexity of propositional and relational credal networks
• Stochastic enumeration method for counting trees
• Version spaces and the consistency problem
• Counting maximal independent sets in directed path graphs
• Cook's versus Valiant's hypothesis
• Some decision and counting problems of the Duquenne-Guigues basis of implications
• Extending matchings in claw-free graphs
• Maximum matchings in scale-free networks with identical degree distribution
• Recognition and dualization of disguised bidual Horn functions.
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• Universal relations and {\#}P-completeness
• Rényi entropies as a measure of the complexity of counting problems
• The operators min and max on the polynomial hierarchy
• A Bayesian approach to relevance in game playing
• A logic-based analysis of Dempster-Shafer theory
• Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems
• Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph
• Querying disjunctive databases through nonmonotonic logics
• Counting minimal unsatisfiable subsets
• Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#\(P\)-complete
• Counting over non-planar graphs
• Polynomial time algorithm for an optimal stable assignment with multiple partners
• Phase transition of multivariate polynomial systems
• On listing, sampling, and counting the chordal graphs with edge constraints
• Computational complexity of impact size estimation for spreading processes on networks
• The computational complexity of QoS measures for orchestrations. The computational complexity of QoS measures
• 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
• Series-parallel posets and the Tutte polynomial
• From 5-pass \(\mathcal {MQ}\)-based identification to \(\mathcal {MQ}\)-based signatures
• Lifted inference with tree axioms
• Polynomial-time compression
• A probabilistic logic programming event calculus
• Spanning trees of 3-uniform hypergraphs

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)