The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected

From MaRDI portal
Publication:3036719

DOI10.1137/0212053zbMath0524.68041OpenAlexW1998076865WikidataQ59442844 ScholiaQ59442844MaRDI QIDQ3036719

Michael O. Ball, J. Scott Provan

Publication date: 1983

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0212053



Related Items

Information enhancement -- a tool for approximate representation of optimal strategies from influence diagrams, Uniform Reliability of Self-Join-Free Conjunctive Queries, On edge cut of graphs leaving components of order at least five, A Graph Polynomial for Independent Sets of Bipartite Graphs, A Dichotomy Theorem for Polynomial Evaluation, The computational complexity of probabilistic inference using Bayesian belief networks, A bound on 4-restricted edge connectivity of graphs, Hard Enumeration Problems in Geometry and Combinatorics, Counting Small Induced Subgraphs Satisfying Monotone Properties, Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain, Connectivity of finite anisotropic random graphs and directed graphs, Finding a Level Ideal of a Poset, Oblivious bounds on the probability of boolean functions, Exact solutions in low-rank approximation with zeros, On the Tractability of SHAP Explanations, Algebraic Methods Applied to Network Reliability Problems, A method to calculate the number of spanning connected unicyclic(bicyclic) subgraphs in 2-separable networks, On the hardness of approximate reasoning, Reliability analysis on the multiple-loop network, Polynomial-time algorithms for multimarginal optimal transport problems with structure, The firebreak problem, Exact reliability optimization for series‐parallel graphs using convex envelopes, On the reliability estimation of stochastic binary systems, Approximately counting independent sets in bipartite graphs via graph containers, On the set of stable matchings in a bipartite graph, Counting almost minimum cutsets with reliability applications, Uniformly optimally reliable graphs: A survey, Network reliability: Heading out on the highway, On the split reliability of graphs, On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts, Wang-Landau sampling for estimation of the reliability of physical networks, On measuring inconsistency in definite and indefinite databases with denial constraints, A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases, Unnamed Item, Gorenstein braid cones and crepant resolutions, Counting independent sets in tricyclic graphs, Reliability of task graph schedules with transient and fail-stop failures: complexity and algorithms, Hardness of computing width parameters based on branch decompositions over the vertex set, Network Resilience, Counting Minimal Dominating Sets, Unnamed Item, Counting Constraint Satisfaction Problems., INDEPENDENT SETS FROM AN ALGEBRAIC PERSPECTIVE, Hardness of computing width parameters based on branch decompositions over the vertex set, Generalized loop‐erased random walks and approximate reachability, The cross-entropy method for network reliability estimation, A novel algorithm on network reliability estimation, The distributed program reliability analysis on ring-type topologies, On optimally-\(\lambda^{(3)}\) transitive graphs, Super restricted edge connectivity of regular graphs, Counting independent sets in graphs with bounded bipartite pathwidth, On the characterization of the domination of a diameter-constrained network reliability model, Unnamed Item, Algorithmic combinatorics based on slicing posets, Neighborhood conditions for graphs to be super restricted edge connected, The Exponential Time Complexity of Computing the Probability That a Graph Is Connected, Unnamed Item, Computational aspects of mining maximal frequent patterns, Estimation of all-terminal network reliability using an artificial neural network, Suboptimal cuts: Their enumeration, weight and number, The Generalized Median Stable Matchings: Finding Them Is Not That Easy, Full complexity analysis of the diameter-constrained reliability, Horn representation of a concept lattice, On the computational complexity of the Jones and Tutte polynomials, High-confidence estimation of small s -t reliabilities in directed acyclic networks, How fast can we reach a target vertex in stochastic temporal graphs, MULTI-TERMINAL NETWORK CONNECTEDNESS ON SERIES-PARALLEL NETWORKS, A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability, Integrating and Sampling Cuts in Bounded Treewidth Graphs, Unnamed Item, Consecutive-2 systems on trees, An Evolution Model for Monte Carlo Estimation of Equilibrium Network Renewal Parameters, Subtractive reductions and complete problems for counting complexity classes, The complexity of approximating the complex-valued Potts model, Transducing Markov sequences, On Generalized Comparison-Based Sorting Problems, Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth, The complexity of solution-free sets of integers for general linear equations, A proof of an inequality concerning \(k\)-restricted edge connectivity, Edge cuts leaving components of order at least \(m\), Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin–Marsten bounding, Onm-restricted edge connectivity of undirected generalized De Bruijn graphs, Complexity of model checking for reaction systems, The complexity of approximating the complex-valued Potts model, Parametric max flow problems in a class of networks with series-parallel structure, An analysis of Monte Carlo algorithms for counting problems, On the equivalence in complexity among three computation problems on maximum number of edge-disjoint \(s\)-\(t\) paths in a probabilistic graph, The complexity of counting locally maximal satisfying assignments of Boolean CSPs, Unique entity estimation with application to the Syrian conflict, The computational complexity of the reliability problem on distributed systems, An algorithm to generate the ideals of a partial order, On the computational complexity of the order polynomial, Counting independent sets and maximal independent sets in some subclasses of bipartite graphs, Matroid Steiner problems, the Tutte polynomial and network reliability, Fast computation of bounds for two-terminal network reliability, Counting \(4 \times 4\) matrix partitions of graphs, Fast and simple algorithms to count the number of vertex covers in an interval graph, Secure overlay network design, Reliability properties of the hypercube network, Heuristic maximization of the number of spanning trees in regular graphs, An application of the planar separator theorem to counting problems, Edge-packings of graphs and network reliability, Lower bounds on two-terminal network reliability, Counting solutions to binomial complete intersections, Towards a dichotomy theorem for the counting constraint satisfaction problem, On maximal 3-restricted edge connectivity and reliability analysis of hypercube networks, Linear-time algorithms for counting independent sets in bipartite permutation graphs, On super restricted edge connectivity of half vertex transitive graphs, A dichotomy in the complexity of counting database repairs, Closest pair and the post office problem for stochastic points, The complexity of approximating complex-valued Ising and Tutte partition functions, The average reliability of a graph, Counting and enumerating preferred database repairs, Factorization of network reliability with perfect nodes. I: Introduction and statements, How fast can we reach a target vertex in stochastic temporal graphs?, On optimizing edge connectivity of product graphs, Search for all \(d\)-mincuts of a limited-flow network, The approximability of multiple facility location on directed networks with random arc failures, Simple linear-time algorithms for counting independent sets in distance-hereditary graphs, The complexity of approximately counting stable roommate assignments, The complexity of approximately counting stable matchings, The complexity of Bayesian networks specified by propositional and relational languages, A logic-based analysis of Dempster-Shafer theory, Probabilistic query answering over inconsistent databases, Graph theoretic characterization and reliability of the multiple-clique network, Understanding the generalized median stable matchings, Linear-time algorithms for computing the reliability of bipartite and (\(\# \leqslant 2\)) star distributed computing systems., On the complexity of dynamic programming for sequencing problems with precedence constraints, Fair cost allocations under conflicts - a game-theoretic point of view -, Counting independent sets in cocomparability graphs, Counting subset repairs with functional dependencies, Fine-grained dichotomies for the Tutte plane and Boolean \#CSP, Counting and sampling minimum cuts in genus \(g\) graphs, Reliability covering problems for hypergraphs, Fast sequential importance sampling to estimate the graph reliability polynomial, Computing on binary strings, Counting independent sets in a tolerance graph, Invulnerability of planar two-tree networks, Counting the number of independent sets in chordal graphs, Counting linear extensions, End-to-end availability-dependent pricing of network services, A note on bounding \(k\)-terminal reliability, Faster exponential-time algorithms for approximately counting independent sets, Restricted connectivity for some interconnection networks, Note on complexity of computing the domination of binary systems, On the complexity of generalized chromatic polynomials, Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization, Reliable assignments of processors to tasks and factoring on matroids, A new fixed point approach for stable networks and stable marriages, Complexity issues for the sandwich homogeneous set problem, 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, Obtainable sizes of topologies on finite sets, Dichotomy results for fixed point counting in Boolean dynamical systems, A proof of unimodality on the numbers of connected spanning subgraphs in an \(n\)-vertex graph with at least \(\left\lceil (3-2\sqrt 2) n^2 + n - \frac {7-2\sqrt 2}{2 \sqrt 2}\right\rceil\) edges, On estimating the number of order ideals in partial orders, with some applications, The homotopy classes of continuous maps between some nonmetrizable manifolds, Approximation algorithm for estimating failure probability of multipath transmission, On the generation of circuits and minimal forbidden sets, \(\lambda ^{\prime}\)-optimal digraphs, Counting maximal independent sets in directed path graphs, Computational complexity of impact size estimation for spreading processes on networks, Counting the number of vertex covers in a trapezoid graph, Topological optimization of reliable networks under dependent failures, The parameterized complexity of \(k\)-edge induced subgraphs, Counting independent sets in tree convex bipartite graphs, On 3-restricted edge connectivity of undirected binary Kautz graphs, Resource-constrained project scheduling: Notation, classification, models, and methods, Series-parallel posets and the Tutte polynomial, Best- and worst-case variances when bounds are available for the distribution function., Enumeration aspects of maximal cliques and bicliques, Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time, Expected reliability of communication protocols, Reliable wireless multimedia sensor network design: comparison of hybrid metaheuristics and a matheuristic, Approximate weighted model integration on DNF structures, Query answering over inconsistent knowledge bases: a probabilistic approach, Balancing \(U\)-lines in a multiple \(U\)-line facility, The complexity of counting homeomorphs, The expected number of pairs of connected nodes: Pair-connected reliability, Network flow and 2-satisfiability, The maximum clique problem, Computational complexity of loss networks