The Complexity of Enumeration and Reliability Problems
From MaRDI portal
Publication:3853129
DOI10.1137/0208032zbMath0419.68082WikidataQ55878545 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 complexity; enumeration; counting problems; probabilistic network; completeness results; counting maximal cliques; counting perfect matchings in bipartite graphs; counting trees in a connected graph
68Q25: Analysis of algorithms and problem complexity
05C05: Trees
05C30: Enumeration in graph theory
03D15: Complexity of computation (including implicit computational complexity)
94C15: Applications of graph theory to circuits and networks
05C40: Connectivity
Related Items
The Computational Complexity of the Tutte Plane: the Bipartite Case, On generating all solutions of generalized satisfiability problems, Counting Unlabelled Subtrees of a Tree is #P-complete, UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS, On the computational complexity of the Jones and Tutte polynomials, Rational transductions and complexity of counting problems, Residual reliability of P-threshold graphs, On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions, Unnamed Item, Search for MC in modified networks, Counting and Gröbner bases, The distributed program reliability analysis on ring-type topologies, Counting over non-planar graphs, Decision lists and related Boolean functions, Algorithms for four variants of the exact satisfiability problem, Tight lower bounds on the ambiguity of strong, total, associative, one-way functions, Algorithmic uses of the Feferman-Vaught theorem, Mathematical aspects of concept analysis, Note on complexity of computing the domination of binary systems, Computing residual connectedness reliability for restricted networks, Weak minimization of DFA -- an algorithm and applications, Lower bounds and the hardness of counting properties, A Bayesian approach to relevance in game playing, The complexity of controlled selection, The complexity of computing the number of strings of given length in context-free languages, The computational complexity of abduction, Counting linear extensions, Restricted relativizations of probabilistic polynomial time, A note on bounding \(k\)-terminal reliability, On integer points in polyhedra, Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P, Polynomial-time compression, A very hard log-space counting class, The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable, A catalog of minimally nonideal matrices, The computational complexity of knot and matroid polynomials, The maximum clique problem, Computational complexity of loss networks, The complexity of computing maximal word functions, Extending matchings in claw-free graphs, Finding all the perfect matchings in bipartite graphs, Counting trees in a graph is \(\# \text{P}\)-complete, Simple characterizations of \(P(\# P)\) and complete problems, On the equivalence in complexity among three computation problems on maximum number of edge-disjoint \(s\)-\(t\) paths in a probabilistic graph, On closure properties of GapP, Algorithms to count paths and cycles, The complexities of the coefficients of the Tutte polynomial, Querying disjunctive databases through nonmonotonic logics, A short certificate of the number of universal optimal strategies for stopping simple stochastic games, On the complexity of partially observed Markov decision processes, Polynomial-time inference of all valid implications for Horn and related formulae, Computing optimal assignments for residual network reliability, Metafinite model theory, Two-path subsets: Efficient counting and applications to performability analysis, The complexity of the characteristic and the minimal polynomial., The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes., Linear-time algorithms for computing the reliability of bipartite and (\(\# \leqslant 2\)) star distributed computing systems., The Go polynomials of a graph., Bicycle dimension and special points of the Tutte polynomial, A second step towards complexity-theoretic analogs of Rice's Theorem, Domination of cyclic monotone \((s,t)\)-graphs, On the generation of circuits and minimal forbidden sets, Counting models for 2SAT and 3SAT formulae, An analogue of Hoffman's circulation conditions for max-balanced flows, Series-parallel posets and the Tutte polynomial, The complexity of computing the Tutte polynomial on transversal matroids, Recognition and dualization of disguised bidual Horn functions., Tally NP sets and easy census functions., Unification algorithms cannot be combined in polynomial time., Quorum systems constructed from combinatorial designs, Nonerasing, counting, and majority over the linear time hierarchy, Complexity of learning in concept lattices from positive and negative examples, Counting consistent phylogenetic trees is \#P-complete, On edge transitivity of directed graphs, Heuristic enhancements of the search for the generation of all perfect matchings, A semantic tree algorithm for the generation of sextet polynomials of hexagonal systems, Cook's versus Valiant's hypothesis, A complexity theory for feasible closure properties, Counting for satisfiability by inverting resolution, A novel algorithm on network reliability estimation, Subtractive reductions and complete problems for counting complexity classes, Unnamed Item
