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)

• On the concentration of the number of solutions of random satisfiability formulas
• Towards fixed-parameter tractable algorithms for abstract argumentation
• Approximately counting approximately-shortest paths in directed acyclic graphs
• 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
• The maximum clique problem
• The complexity of computing the permanent
• The computational complexity of maximization and integration
• Approximately counting paths and cycles in a graph
• Counting the number of vertex covers in a trapezoid graph
• A very hard log-space counting class
• Tractable counting of the answers to conjunctive queries
• The complexity of weighted Boolean \#CSP with mixed signs
• Unification algorithms cannot be combined in polynomial time
• The complexity of counting locally maximal satisfying assignments of Boolean CSPs
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• The complexity of colouring problems on dense graphs
• Generating all vertices of a polyhedron is hard
• The computational complexity of the reliability problem on distributed systems
• Counting Small Induced Subgraphs Satisfying Monotone Properties
• Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs
• Finding all the perfect matchings in bipartite graphs
• Polynomial-time inference of all valid implications for Horn and related formulae
• Sequential Monte Carlo for counting vertex covers in general graphs
• Generating and enumerating digitally convex sets of trees
• Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations
• Decision lists and related Boolean functions
• Complexity of counting the optimal solutions
• Counting linear extensions
• On the counting complexity of propositional circumscription
• Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
• On the generation of circuits and minimal forbidden sets
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Power Indices in Spanning Connectivity Games
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• Holographic algorithms by Fibonacci gates
• Computing convex hulls and counting integer points with \texttt{polymake}
• Fast domino tileability
• Counting \(4 \times 4\) matrix partitions of graphs
• Holant problems for 3-regular graphs with complex edge functions
• The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
• Counting Hamiltonian cycles in bipartite graphs
• 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
• An analysis of Monte Carlo algorithms for counting problems
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• On the complexity of inconsistency measurement
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• Parallel computation with threshold functions
• Edge-packings of graphs and network reliability
• Counting models for 2SAT and 3SAT formulae
• A catalog of minimally nonideal matrices
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Well–definedness and efficient inference for probabilistic logic programming under the distribution semantics
• Probabilistic (logic) programming concepts
• Generalized loop-erased random walks and approximate reachability
• High-confidence estimation of small \(s-t\) reliabilities in directed acyclic networks
• Triadic formal concept analysis and triclustering: searching for optimal patterns
• End-to-end availability-dependent pricing of network services
• Computational aspects of monotone dualization: a brief survey
• Simulating cardinal preferences in Boolean games: a proof technique
• Complexity of learning in concept lattices from positive and negative examples
• Metafinite model theory
• The distributed program reliability analysis on ring-type topologies
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Subtractive reductions and complete problems for counting complexity classes
• On the hardness of approximate reasoning
• Lower bounds on two-terminal network reliability
• Holographic reduction, interpolation and hardness
• Graph factors and factorization: 1985--2003: a survey
• On integer points in polyhedra
• Scalable influence maximization for independent cascade model in large-scale social networks
• Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
• Pfaffian orientations and perfect matchings of scale-free networks
• Computational complexity of counting problems on 3-regular planar graphs
• The complexity of computing the number of strings of given length in context-free languages
• Computational complexity of stochastic programming problems
• On the computational complexity of the Jones and Tutte polynomials
• On generating all solutions of generalized satisfiability problems
• Counting and enumeration complexity with application to multicriteria scheduling
• Queries and materialized views on probabilistic databases
• The complexity of approximating bounded-degree Boolean \(\#\)CSP
• Consecutive-2 systems on trees
• Closest pair and the post office problem for stochastic points
• 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

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)