The Complexity of Enumeration and Reliability Problems
From MaRDI portal
Publication:3853129
DOI10.1137/0208032zbMath0419.68082DBLPjournals/siamcomp/Valiant79OpenAlexW2115826669WikidataQ55878545 ScholiaQ55878545MaRDI QIDQ3853129
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
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Enumeration in graph theory (05C30) Complexity of computation (including implicit computational complexity) (03D15) Applications of graph theory to circuits and networks (94C15) Connectivity (05C40)
Related Items (only showing first 100 items - show all)
A complexity theory for feasible closure properties ⋮ On locally most reliable three-terminal graphs of sparse graphs ⋮ Polynomial time algorithm for an optimal stable assignment with multiple partners ⋮ Optimal inter-object correlation when replicating for availability ⋮ Completeness, approximability and exponential time results for counting problems with easy decision version ⋮ New upper bound for the \#3-SAT problem ⋮ On the number of go positions on lattice graphs ⋮ Satisfiability with index dependency ⋮ Computational complexity of counting problems on 3-regular planar graphs ⋮ A Dichotomy Theorem for Polynomial Evaluation ⋮ Dempster's rule of combination is {\#}P-complete ⋮ On stability of a formal concept ⋮ Counting for satisfiability by inverting resolution ⋮ Phase transitions of PP-complete satisfiability problems ⋮ On the complexity of finding shortest variable disjunction branch-and-bound proofs ⋮ Computing convex hulls and counting integer points with \texttt{polymake} ⋮ On the concentration of the number of solutions of random satisfiability formulas ⋮ Unnamed Item ⋮ The effect of combination functions on the complexity of relational Bayesian networks ⋮ On the connection between interval size functions and path counting ⋮ On Sampling Simple Paths in Planar Graphs According to Their Lengths ⋮ A method to calculate the number of spanning connected unicyclic(bicyclic) subgraphs in 2-separable networks ⋮ Counting dominating sets in some subclasses of bipartite graphs ⋮ A general purpose algorithm for counting simple cycles and simple paths of any length ⋮ On the hardness of approximate reasoning ⋮ A dichotomy for bounded degree graph homomorphisms with nonnegative weights ⋮ From 5-Pass $$\mathcal {MQ}$$-Based Identification to $$\mathcal {MQ}$$-Based Signatures ⋮ Solving projected model counting by utilizing treewidth and its limits ⋮ Lifted discriminative learning of probabilistic logic programs ⋮ The approximability of multiple facility location on directed networks with random arc failures ⋮ Target users' activation probability maximization with different seed set constraints in social networks ⋮ Efficient and effective influence maximization in social networks: a hybrid-approach ⋮ Reliability of task graph schedules with transient and fail-stop failures: complexity and algorithms ⋮ Barnette's conjecture through the lens of the \(Mod_k P\) complexity classes ⋮ Fixed-parameter tractable algorithms for tracking shortest paths ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ On random generation of fuzzy measures ⋮ Counting near-perfect matchings on \(C_m \times C_n\) tori of odd order in the Maple system ⋮ Exploiting independent subformulas: a faster approximation scheme for \(\# k\)-SAT ⋮ The computational complexity of random serial dictatorship ⋮ Predecessor existence problems for finite discrete dynamical systems ⋮ Location of zeros for the partition function of the Ising model on bounded degree graphs ⋮ The Power of Self-Reducibility: Selectivity, Information, and Approximation ⋮ Computational complexity of three-dimensional discrete tomography with missing data ⋮ Rényi entropies as a measure of the complexity of counting problems ⋮ Cook's versus Valiant's hypothesis ⋮ On variable-weighted exact satisfiability problems ⋮ The complexity of two problems on arithmetic circuits ⋮ Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width ⋮ Lee-Yang theorems and the complexity of computing averages ⋮ Rumor correction maximization problem in social networks ⋮ Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron. ⋮ Dichotomy results for fixed point counting in Boolean dynamical systems ⋮ Optimal testing for planted satisfiability problems ⋮ A novel algorithm on network reliability estimation ⋮ Not all FPRASs are equal: demystifying FPRASs for DNF-counting ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets ⋮ Counting substrate cycles in topologically restricted metabolic networks ⋮ Learning expressions and programs over monoids ⋮ Computational complexity of stochastic programming problems ⋮ Counting maximal independent sets in directed path graphs ⋮ Network reliability and acyclic orientations ⋮ Permanental generating functions and sequential importance sampling ⋮ Counting the number of solutions for instances of satisfiability ⋮ A survey of some network reliability analysis and synthesis results ⋮ Exponential Time Complexity of Weighted Counting of Independent Sets ⋮ The Exponential Time Complexity of Computing the Probability That a Graph Is Connected ⋮ Minimum budget for misinformation blocking in online social networks ⋮ Community based acceptance probability maximization for target users on social networks: algorithms and analysis ⋮ Computational aspects of mining maximal frequent patterns ⋮ Parameterized counting of partially injective homomorphisms ⋮ Pfaffian orientations and perfect matchings of scale-free networks ⋮ Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity ⋮ An improved algorithm for finding all upper boundary points in a stochastic-flow network ⋮ Counting \(K_4\)-subdivisions ⋮ Counting Subgraphs in Relational Event Graphs ⋮ Full complexity analysis of the diameter-constrained reliability ⋮ Cognitively-constrained learning from neighbors ⋮ Solution-Graphs of Boolean Formulas and Isomorphism ⋮ High-confidence estimation of small s -t reliabilities in directed acyclic networks ⋮ Path puzzles: discrete tomography with a path constraint is hard ⋮ Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs ⋮ Computing the execution probability of jobs with replication in mixed-criticality schedules ⋮ Clar structures vs Fries structures in hexagonal systems ⋮ On the complexity of inconsistency measurement ⋮ Abduction with probabilistic logic programming under the distribution semantics ⋮ Subtractive reductions and complete problems for counting complexity classes ⋮ Computing the probability of getting infected: on the counting complexity of bootstrap percolation ⋮ Time Windowed Data Structures for Graphs ⋮ Combinatorial properties of Farey graphs ⋮ The complexity of solution-free sets of integers for general linear equations ⋮ Belief propagation on the random \(k\)-SAT model ⋮ Computing the \(K\)-terminal reliability of directed path graphs ⋮ Counting Hamiltonian cycles in bipartite graphs ⋮ On the number of perfect matchings in the line graph of a traceable graph ⋮ Classical simulation of quantum circuits by half Gauss sums ⋮ Improved inapproximability results for counting independent sets in the hard-core model ⋮ On the usefulness of linear modular arithmetic in constraint programming
This page was built for publication: The Complexity of Enumeration and Reliability Problems
