The Complexity of Enumeration and Reliability Problems
From MaRDI portal
Publication:3853129
DOI10.1137/0208032zbMath0419.68082OpenAlexW2115826669WikidataQ55878545 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
A Study of Symmetry Breaking Predicates and Model Counting, Completeness Results for Counting Problems with Easy Decision, UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS, Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs, On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions, The operators min and max on the polynomial hierarchy, Nonlevelable sets and immune sets in the accepting density hierarchy inNP, MARKOV CHAIN METHOD FOR COMPUTING THE RELIABILITY OF HAMMOCK NETWORKS, Well–definedness and efficient inference for probabilistic logic programming under the distribution semantics, Hard Enumeration Problems in Geometry and Combinatorics, Unnamed Item, Model Counting of Monotone Conjunctive Normal Form Formulas with Spectra, Counting Small Induced Subgraphs Satisfying Monotone Properties, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, The Computational Complexity of the Tutte Plane: the Bipartite Case, The Rank-One Quadratic Assignment Problem, MAXIMUM MATCHINGS IN A PSEUDOFRACTAL SCALE-FREE WEB, Rational transductions and complexity of counting problems, Algebraic Methods Applied to Network Reliability Problems, On the expansion of combinatorial polytopes, Rational transductions and complexity of counting problems, Polynomial-time algorithms for multimarginal optimal transport problems with structure, On the dimer problem of the vertex-edge graph of a cubic graph, An Exact Method for the Minimum Feedback Arc Set Problem, A probabilistic logic programming event calculus, Counting almost minimum cutsets with reliability applications, A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances, Permutations with Restricted Displacement, Complexity of Counting the Optimal Solutions, On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints, Unnamed Item, Classifying the computational complexity of problems, Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models, Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs, Counting Complexity of Minimal Cardinality and Minimal Weight Abduction, Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms, On the Complexity of Holant Problems, Counting Constraint Satisfaction Problems., MAP Inference for Probabilistic Logic Programming, Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing, Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model, VERTEX DECOMPOSITION TO CALCULATE THE NETWORK PROBABILISTIC CONNECTIVITY, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, Unification algorithms cannot be combined in polynomial time, Beyond non-backtracking: non-cycling network centrality measures, Generalized loop‐erased random walks and approximate reachability, A Structure Theorem for Rooted Binary Phylogenetic Networks and Its Implications for Tree-Based Networks, Languages Accepted by Weighted Restarting Automata*, Search for MC in modified networks, Monomer-dimer problem on random planar honeycomb lattice, On the power of parity polynomial time, On generating all solutions of generalized satisfiability problems, Counting and Gröbner bases, Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP, The distributed program reliability analysis on ring-type topologies, Residual reliability of P-threshold graphs, Counting over non-planar graphs, Unnamed Item, Unnamed Item, Unnamed Item, On the Complexity of Computing Generators of Closed Sets, Unnamed Item, Decision lists and related Boolean functions, On the parameterized complexity of approximate counting, Phase transition of multivariate polynomial systems, Counting dominating sets in generalized series-parallel graphs, On the computational complexity of the Jones and Tutte polynomials, Counting and enumeration complexity with application to multicriteria scheduling, Generating all vertices of a polyhedron is hard, Power Indices in Spanning Connectivity Games, Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction, Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors, Counting of Teams in First-Order Team Logics, MULTI-TERMINAL NETWORK CONNECTEDNESS ON SERIES-PARALLEL NETWORKS, Fixed Point Approximations for Retrial Networks, A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability, Unnamed Item, Unnamed Item, Full Hermite interpolation of the reliability of a hammock network, ON THE COMPLEXITY OF COUNTING FIXED POINTS AND GARDENS OF EDEN IN SEQUENTIAL DYNAMICAL SYSTEMS ON PLANAR BIPARTITE GRAPHS, FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS, Unnamed Item, Consecutive-2 systems on trees, Sensitivity Analysis for the System Reliability Function, Bounds on the Reliability Polynomial for Shellable Independence Systems, Unnamed Item, SELF-SPECIFYING MACHINES, THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY, Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?, Flows with Unit Path Capacities and Related Packing and Covering Problems, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results, Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model, Unnamed Item, Sequential stratified splitting for efficient Monte Carlo integration, Fast and simple algorithms for counting dominating sets in distance-hereditary graphs, Solution-Graphs of Boolean Formulas and Isomorphism1, Counting Unlabelled Subtrees of a Tree is #P-complete, Adaptive Bin Packing with Overflow, EDGE DOMINATION NUMBER AND THE NUMBER OF MINIMUM EDGE DOMINATING SETS IN PSEUDOFRACTAL SCALE-FREE WEB AND SIERPIŃSKI GASKET, On computing minimal independent support and its applications to sampling and counting, Monte-Carlo algorithms for the planar multiterminal network reliability problem, The complexity of colouring problems on dense graphs, An analysis of Monte Carlo algorithms for counting problems, The complexity of counting locally maximal satisfying assignments of Boolean CSPs, The computational complexity of the reliability problem on distributed systems, Counting minimal unsatisfiable subsets, Sequential Monte Carlo for counting vertex covers in general graphs, Generating and enumerating digitally convex sets of trees, Complexity of counting the optimal solutions, The complexity of weighted Boolean \#CSP with mixed signs, Computational hardness of enumerating groundstates of the antiferromagnetic Ising model in triangulations, Fast domino tileability, Counting \(4 \times 4\) matrix partitions of graphs, Fast and simple algorithms to count the number of vertex covers in an interval graph, A note on observables for counting trails and paths in graphs, Holant problems for 3-regular graphs with complex edge functions, Graph factors and factorization: 1985--2003: a survey, Counting solutions to binomial complete intersections, 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, The complexity of computing the permanent, Towards a dichotomy theorem for the counting constraint satisfaction problem, Tractable counting of the answers to conjunctive queries, Closest pair and the post office problem for stochastic points, Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions, Tensor network contractions for \#SAT, The complexity of complex weighted Boolean \#CSP, The complexity of generalized domino tilings, Triadic formal concept analysis and triclustering: searching for optimal patterns, Decomposition representations of logical equations in problems of inversion of discrete functions, Probabilistic (logic) programming concepts, The challenges of unbounded treewidth in parameterised subgraph counting problems, The complexity of weighted and unweighted \(\#\)CSP, Sparse reliable graph backbones, Model checking in the modal \(\mu \)-calculus and generic solutions, Counting problems and algebraic formal power series in noncommuting variables, A logic-based analysis of Dempster-Shafer theory, Probabilistic query answering over inconsistent databases, On the complexity of ranking, The consequences of eliminating NP solutions, Enumerating Hamiltonian cycles, Counting problems and ranks of matrices, Practical algorithms for MSO model-checking on tree-decomposable graphs, 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, Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs, Complexity of DNF minimization and isomorphism testing for monotone formulas, End-to-end availability-dependent pricing of network services, Some decision and counting problems of the Duquenne-Guigues basis of implications, Computational aspects of monotone dualization: a brief survey, Mathematical aspects of concept analysis, Note on complexity of computing the domination of binary systems, On the complexity of generalized chromatic polynomials, Robust planning with incomplete domain models, Approximately counting paths and cycles in a graph, Universal relations and {\#}P-completeness, Random sampling of colourings of sparse random graphs with a constant number of colours, Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties, On the complexity of propositional and relational credal networks, Stochastic enumeration method for counting trees, The complexity of finding effectors, Computing residual connectedness reliability for restricted networks, Approximation complexity of complex-weighted degree-two counting constraint satisfaction problems, Maximum matchings in scale-free networks with identical degree distribution, On the counting complexity of propositional circumscription, Queries and materialized views on probabilistic databases, Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph, Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#\(P\)-complete, Weak minimization of DFA -- an algorithm and applications, Lower bounds and the hardness of counting properties, On listing, sampling, and counting the chordal graphs with edge constraints, The parameterized complexity of probability amplification, Computational complexity of impact size estimation for spreading processes on networks, Counting complexity of propositional abduction, Spanning trees of 3-uniform hypergraphs, Counting the number of vertex covers in a trapezoid graph, The parameterized complexity of \(k\)-edge induced subgraphs, Generating 3-vertex connected spanning subgraphs, Counting independent sets in tree convex bipartite graphs, Listing minimal edge-covers of intersecting families with applications to connectivity problems, Regular expression order-sorted unification and matching, Compressing probabilistic Prolog programs, From a zoo to a zoology: Towards a general theory of graph polynomials, Enumeration aspects of maximal cliques and bicliques, A rigorous methodology for specification and verification of business processes, The counting complexity of a simple scheduling problem, On counting 3-D matchings of size \(k\), Flows with unit path capacities and related packing and covering problems, Monomial bases for broken circuit complexes, The computational complexity of maximization and integration, The complexity of counting homeomorphs, On some natural complete operators, A note on enumerative counting, Version spaces and the consistency problem, 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, 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, Smoothed counting of 0–1 points in polyhedra, Fast reliability ranking of matchstick minimal networks, Exact reliability optimization for series‐parallel graphs using convex envelopes, The number of satisfying assignments of random 2‐SAT formulas, Dr. Charles L. Suffel: Scholar, teacher, mentor, friend, Uniformly optimally reliable graphs: A survey, Network reliability: Heading out on the highway, Lifted inference with tree axioms, Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality, Opinion influence maximization problem in online social networks based on group polarization effect, Compression with wildcards: Abstract simplicial complexes, Discrete Optimal Transport with Independent Marginals is #P-Hard, COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB, Parameterized Counting and Cayley Graph Expanders, Projected model counting: beyond independent support, On the complexity of computational problems associated with simple stochastic games, Structure of single-peaked preferences, Enumeration of perfect matchings of the middle graph of a graph \(G\) with \(\triangle (G) \leq 4\), Social disruption games in signed networks, Picturing Counting Reductions with the ZH-Calculus, Unnamed Item, Uniformly most reliable three-terminal graph of dense graphs, Some observations on holographic algorithms, Complexity of learning in concept lattices from positive and negative examples, Counting trees in a graph is \(\# \text{P}\)-complete, Simple characterizations of \(P(\# P)\) and complete problems, On the construction of parallel computers from various basis of Boolean functions, On the equivalence in complexity among three computation problems on maximum number of edge-disjoint \(s\)-\(t\) paths in a probabilistic graph, The fewest clues problem, On closure properties of GapP, Counting consistent phylogenetic trees is \#P-complete, Counting independent sets and maximal independent sets in some subclasses of bipartite graphs, Algorithms to count paths and cycles, Approximation to measurable functions and its relation to probabilistic computation, On blockwise symmetric matchgate signatures and higher domain \#CSP, The complexities of the coefficients of the Tutte polynomial, On edge transitivity of directed graphs, Querying disjunctive databases through nonmonotonic logics, A short certificate of the number of universal optimal strategies for stopping simple stochastic games, Simulating cardinal preferences in Boolean games: a proof technique, On the complexity of partially observed Markov decision processes, Some observations on the connection between counting and recursion, Polynomial-time inference of all valid implications for Horn and related formulae, Enumerative techniques for solving some nonconvex global optimization problems, The stochastic stability of decentralized matching on a graph, Parallel computation with threshold functions, An application of the planar separator theorem to counting problems, Computing optimal assignments for residual network reliability, Edge-packings of graphs and network reliability, Lower bounds on two-terminal network reliability, Approximate counting, uniform generation and rapidly mixing Markov chains, Heuristic enhancements of the search for the generation of all perfect matchings, Linear-time algorithms for counting independent sets in bipartite permutation graphs, Metafinite model theory, A Bayesian approach to relevance in game playing, Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs, Holographic reduction, interpolation and hardness, The computational complexity of QoS measures for orchestrations. The computational complexity of QoS measures, Understanding the complexity of axiom pinpointing in lightweight description logics, Holographic algorithms by Fibonacci gates, Two-path subsets: Efficient counting and applications to performability analysis, The complexity of approximating bounded-degree Boolean \(\#\)CSP, Combinatorial problems over power sets, The complexity of the characteristic and the minimal polynomial., The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes., Search for all \(d\)-mincuts of a limited-flow network, Holographic reduction for some counting problems, Scalable influence maximization for independent cascade model in large-scale social networks, Sulla complessita di alcuni problemi di conteggio, Parameterized random complexity, Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket, Simple linear-time algorithms for counting independent sets in distance-hereditary graphs, Improved mixing condition on the grid for counting and sampling independent sets, The complexity of Bayesian networks specified by propositional and relational languages, The complexity of problems for quantified constraints, Linear-time algorithms for computing the reliability of bipartite and (\(\# \leqslant 2\)) star distributed computing systems., Number of spanning trees of different products of complete and complete bipartite graphs, A semantic tree algorithm for the generation of sextet polynomials of hexagonal systems, The Go polynomials of a graph., On counting problems and the polynomial-time hierarchy, Enumerating the cycles of a digraph: a new preprocessing strategy, 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, Stochastic enumeration with importance sampling, Restricted relativizations of probabilistic polynomial time, A note on bounding \(k\)-terminal reliability, The query complexity of a permutation-based variant of mastermind, On integer points in polyhedra, Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P, An efficient algorithm for link prediction in temporal uncertain social networks, Polynomial-time compression, Maximizing misinformation restriction within time and budget constraints, Uniquely pressable graphs: characterization, enumeration, and recognition, Towards fixed-parameter tractable algorithms for abstract argumentation, A very hard log-space counting class, On the generation of circuits and minimal forbidden sets, Counting models for 2SAT and 3SAT formulae, Closest paths in graph drawings under an elastic metric, An analogue of Hoffman's circulation conditions for max-balanced flows, Series-parallel posets and the Tutte polynomial, The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable, Voronoi diagrams with barriers and on polyhedra for minimal path planning, Enumerative counting is hard, Bicycle dimension and special points of the Tutte polynomial, A second step towards complexity-theoretic analogs of Rice's Theorem, Randomised algorithms, Domination of cyclic monotone \((s,t)\)-graphs, The complexity of computing the Tutte polynomial on transversal matroids, A catalog of minimally nonideal matrices, 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, 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
