The Complexity of Enumeration and Reliability Problems
From MaRDI portal
Publication:3853129
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
computational complexityenumerationcounting problemsprobabilistic networkcompleteness resultscounting maximal cliquescounting perfect matchings in bipartite graphscounting trees in a connected graph
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)
- 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
- Random sampling of colourings of sparse random graphs with a constant number of colours
- On the expansion of combinatorial polytopes
- A second step towards complexity-theoretic analogs of Rice's Theorem
- The parameterized complexity of \(k\)-edge induced subgraphs
- Counting independent sets in tree convex bipartite graphs
- Clar structures vs Fries structures in hexagonal systems
- Regular expression order-sorted unification and matching
- Tensor network contractions for \#SAT
- Location of zeros for the partition function of the Ising model on bounded degree graphs
- The Power of Self-Reducibility: Selectivity, Information, and Approximation
- Counting complexity of propositional abduction
- Compressing probabilistic Prolog programs
- A novel algorithm on network reliability estimation
- Title not available (Why is that?)
- Counting problems and algebraic formal power series in noncommuting variables
- Stochastic enumeration with importance sampling
- Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing
- On the complexity of ranking
- Permanental generating functions and sequential importance sampling
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Parameterized random complexity
- Combinatorial problems over power sets
- Dempster's rule of combination is {\#}P-complete
- Bounds on the Reliability Polynomial for Shellable Independence Systems
- On the power of parity polynomial time
- UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
- Complexity of DNF minimization and isomorphism testing for monotone formulas
- A note on enumerative counting
- The complexity of problems for quantified constraints
- Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
- Uniquely pressable graphs: characterization, enumeration, and recognition
- Enumerative techniques for solving some nonconvex global optimization problems
- Note on complexity of computing the domination of binary systems
- On the complexity of generalized chromatic polynomials
- Not all FPRASs are equal: demystifying FPRASs for DNF-counting
- Counting near-perfect matchings on \(C_m \times C_n\) tori of odd order in the Maple system
- On the number of perfect matchings in the line graph of a traceable graph
- Classical simulation of quantum circuits by half Gauss sums
- On the usefulness of linear modular arithmetic in constraint programming
- Combinatorial properties of Farey graphs
- Rumor correction maximization problem in social networks
- Computational complexity of three-dimensional discrete tomography with missing data
- On the number of go positions on lattice graphs
- On hashing-based approaches to approximate DNF-counting
- Optimal testing for planted satisfiability problems
- Counting of Teams in First-Order Team Logics
- Counting substrate cycles in topologically restricted metabolic networks
- On locally most reliable three-terminal graphs of sparse graphs
- Efficient and effective influence maximization in social networks: a hybrid-approach
- Solving projected model counting by utilizing treewidth and its limits
- Completeness results for counting problems with easy decision
- ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS
- Completeness, approximability and exponential time results for counting problems with easy decision version
- Parameterized counting of partially injective homomorphisms
- Time windowed data structures for graphs
- Community based acceptance probability maximization for target users on social networks: algorithms and analysis
- On the connection between interval size functions and path counting
- Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
- An improved algorithm for finding all upper boundary points in a stochastic-flow network
- Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
- On the complexity of finding shortest variable disjunction branch-and-bound proofs
- Minimum budget for misinformation blocking in online social networks
- Sequential stratified splitting for efficient Monte Carlo integration
- The number of satisfying assignments of random 2‐SAT formulas
- Monomer-dimer problem on random planar honeycomb lattice
- Counting homomorphisms modulo a prime number
- Lifted discriminative learning of probabilistic logic programs
- Uniformly most reliable three-terminal graph of dense graphs
- Computing the execution probability of jobs with replication in mixed-criticality schedules
- Parameterized Counting and Cayley Graph Expanders
- MAP inference for probabilistic logic programming
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
- A semantic tree algorithm for the generation of sextet polynomials of hexagonal systems
- Abduction with probabilistic logic programming under the distribution semantics
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)
