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

Cited in

(only showing first 100 items - show all)

Consecutive-2 systems on trees
How fast can we reach a target vertex in stochastic temporal graphs?
Reliable wireless multimedia sensor network design: comparison of hybrid metaheuristics and a matheuristic
On the computational complexity of the order polynomial
A logic-based analysis of Dempster-Shafer theory
A graph polynomial for independent sets of bipartite graphs
Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
Complexity of model checking for reaction systems
A bound on 4-restricted edge connectivity of graphs
A Dichotomy Theorem for Polynomial Evaluation
Search for all \(d\)-mincuts of a limited-flow network
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
The complexity of solution-free sets of integers for general linear equations
Hardness of computing width parameters based on branch decompositions over the vertex set
The cross-entropy method for network reliability estimation
Hard Enumeration Problems in Geometry and Combinatorics
On the Tractability of SHAP Explanations
The maximum clique problem
A new fixed point approach for stable networks and stable marriages
scientific article; zbMATH DE number 7561410 (Why is no real title available?)
The average reliability of a graph
Invulnerability of planar two-tree networks
Horn representation of a concept lattice
The computational complexity of probabilistic inference using Bayesian belief networks
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
Counting subset repairs with functional dependencies
Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization
Counting the number of vertex covers in a trapezoid graph
A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases
On the set of stable matchings in a bipartite graph
Matroid Steiner problems, the Tutte polynomial and network reliability
Polynomial-time algorithms for multimarginal optimal transport problems with structure
On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
An algorithm to generate the ideals of a partial order
Computational complexity of impact size estimation for spreading processes on networks
Transducing Markov sequences
Secure overlay network design
The complexity of counting locally maximal satisfying assignments of Boolean CSPs
Approximation algorithm for estimating failure probability of multipath transmission
Towards a dichotomy theorem for the counting constraint satisfaction problem
Unique entity estimation with application to the Syrian conflict
Series-parallel posets and the Tutte polynomial
The complexity of approximating the complex-valued Potts model
Faster exponential-time algorithms for approximately counting independent sets
Heuristic maximization of the number of spanning trees in regular graphs
The computational complexity of the reliability problem on distributed systems
Counting independent sets and maximal independent sets in some subclasses of bipartite graphs
Wang-Landau sampling for estimation of the reliability of physical networks
Linear-time algorithms for computing the reliability of bipartite and (\(\# \leqslant 2\)) star distributed computing systems.
How fast can we reach a target vertex in stochastic temporal graphs?
Counting Small Induced Subgraphs Satisfying Monotone Properties
Fast computation of bounds for two-terminal network reliability
Counting almost minimum cutsets with reliability applications
Counting linear extensions
The complexity of approximately counting stable roommate assignments
On the reliability estimation of stochastic binary systems
\(\lambda ^{\prime}\)-optimal digraphs
The complexity of approximately counting stable matchings
The parameterized complexity of k-edge induced subgraphs
Counting independent sets in tree convex bipartite graphs
Complexity issues for the sandwich homogeneous set problem
On super restricted edge connectivity of half vertex transitive graphs
On the generation of circuits and minimal forbidden sets
Information enhancement -- a tool for approximate representation of optimal strategies from influence diagrams
Reliability properties of the hypercube network
The homotopy classes of continuous maps between some nonmetrizable manifolds
Probabilistic query answering over inconsistent databases
scientific article; zbMATH DE number 7375995 (Why is no real title available?)
Network flow and 2-satisfiability
The exponential time complexity of computing the probability that a graph is connected
Understanding the generalized median stable matchings
A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
On maximal 3-restricted edge connectivity and reliability analysis of hypercube networks
Counting 4 4 matrix partitions of graphs
Hardness of computing width parameters based on branch decompositions over the vertex set
The expected number of pairs of connected nodes: Pair-connected reliability
Full complexity analysis of the diameter-constrained reliability
Integrating and sampling cuts in bounded treewidth graphs
Oblivious bounds on the probability of boolean functions
An analysis of Monte Carlo algorithms for counting problems
scientific article; zbMATH DE number 2230256 (Why is no real title available?)
Computational complexity of counting coincidences
On the complexity of dynamic programming for sequencing problems with precedence constraints
Estimation of all-terminal network reliability using an artificial neural network
The firebreak problem
Exact reliability optimization for series‐parallel graphs using convex envelopes
On estimating the number of order ideals in partial orders, with some applications
Edge-packings of graphs and network reliability
Counting constraint satisfaction problems
Counting the number of independent sets in chordal graphs
Resource-constrained project scheduling: Notation, classification, models, and methods
Computational complexity of loss networks
Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin-Marsten bounding
The Generalized Median Stable Matchings: Finding Them Is Not That Easy
Super restricted edge connectivity of regular graphs
Counting and sampling minimum cuts in genus \(g\) graphs
Approximately counting independent sets in bipartite graphs via graph containers
Best- and worst-case variances when bounds are available for the distribution function.
Factorization of network reliability with perfect nodes. I: Introduction and statements

This page was built for publication: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3036719)