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

DOI10.1137/0212053zbMATH Open0524.68041DBLPjournals/siamcomp/ProvanB83OpenAlexW1998076865WikidataQ59442844 ScholiaQ59442844MaRDI QIDQ3036719FDOQ3036719

Cited In (only showing first 100 items - show all)

A graph polynomial for independent sets of bipartite graphs
A bound on 4-restricted edge connectivity of graphs
Search for all \(d\)-mincuts of a limited-flow network
Complexity of model checking for reaction systems
Hard Enumeration Problems in Geometry and Combinatorics
The cross-entropy method for network reliability estimation
The maximum clique problem
The computational complexity of probabilistic inference using Bayesian belief networks
The average reliability of a graph
Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization
Counting the number of vertex covers in a trapezoid graph
An algorithm to generate the ideals of a partial order
Approximation algorithm for estimating failure probability of multipath transmission
The complexity of counting locally maximal satisfying assignments of Boolean CSPs
Towards a dichotomy theorem for the counting constraint satisfaction problem
The computational complexity of the reliability problem on distributed systems
Counting Small Induced Subgraphs Satisfying Monotone Properties
Generalized loop‐erased random walks and approximate reachability
Counting almost minimum cutsets with reliability applications
Fast computation of bounds for two-terminal network reliability
Counting linear extensions
The complexity of approximately counting stable roommate assignments
\(\lambda ^{\prime}\)-optimal digraphs
The complexity of approximately counting stable matchings
On super restricted edge connectivity of half vertex transitive graphs
Complexity issues for the sandwich homogeneous set problem
On the generation of circuits and minimal forbidden sets
The homotopy classes of continuous maps between some nonmetrizable manifolds
Probabilistic query answering over inconsistent databases
Understanding the generalized median stable matchings
Network flow and 2-satisfiability
On maximal 3-restricted edge connectivity and reliability analysis of hypercube networks
Counting \(4 \times 4\) matrix partitions of graphs
An analysis of Monte Carlo algorithms for counting problems
On the complexity of dynamic programming for sequencing problems with precedence constraints
Edge-packings of graphs and network reliability
Counting the number of independent sets in chordal graphs
Resource-constrained project scheduling: Notation, classification, models, and methods
Super restricted edge connectivity of regular graphs
Counting and sampling minimum cuts in genus \(g\) graphs
On optimally-\(\lambda^{(3)}\) transitive graphs
INDEPENDENT SETS FROM AN ALGEBRAIC PERSPECTIVE
Fast sequential importance sampling to estimate the graph reliability polynomial
Computing on binary strings
Counting independent sets in a tolerance graph
Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
High-confidence estimation of small \(s-t\) reliabilities in directed acyclic networks
End-to-end availability-dependent pricing of network services
The distributed program reliability analysis on ring-type topologies
Counting independent sets in tricyclic graphs
Fast and simple algorithms to count the number of vertex covers in an interval graph
Counting solutions to binomial complete intersections
An application of the planar separator theorem to counting problems
Subtractive reductions and complete problems for counting complexity classes
On the hardness of approximate reasoning
Lower bounds on two-terminal network reliability
Reliability of task graph schedules with transient and fail-stop failures: complexity and algorithms
Fair cost allocations under conflicts - a game-theoretic point of view -
Restricted connectivity for some interconnection networks
Counting and enumerating preferred database repairs
Dichotomy results for fixed point counting in Boolean dynamical systems
A proof of an inequality concerning \(k\)-restricted edge connectivity
Edge cuts leaving components of order at least \(m\)
Balancing \(U\)-lines in a multiple \(U\)-line facility
Enumeration aspects of maximal cliques and bicliques
On optimizing edge connectivity of product graphs
On 3-restricted edge connectivity of undirected binary Kautz graphs
Reliable assignments of processors to tasks and factoring on matroids
On the characterization of the domination of a diameter-constrained network reliability model
Neighborhood conditions for graphs to be super restricted edge connected
Connectivity of finite anisotropic random graphs and directed graphs
Counting maximal independent sets in directed path graphs
Finding a Level Ideal of a Poset
A dichotomy in the complexity of counting database repairs
Topological optimization of reliable networks under dependent failures
On the computational complexity of the Jones and Tutte polynomials
Queries and materialized views on probabilistic databases
Consecutive-2 systems on trees
Closest pair and the post office problem for stochastic points
Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth
Network Resilience
Expected reliability of communication protocols
Onm-restricted edge connectivity of undirected generalized De Bruijn graphs
Note on complexity of computing the domination of binary systems
On the complexity of generalized chromatic polynomials
Reliable wireless multimedia sensor network design: comparison of hybrid metaheuristics and a matheuristic
How fast can we reach a target vertex in stochastic temporal graphs?
On the computational complexity of the order polynomial
A logic-based analysis of Dempster-Shafer theory
A Dichotomy Theorem for Polynomial Evaluation
Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
Hardness of computing width parameters based on branch decompositions over the vertex set
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
On the Tractability of SHAP Explanations
The complexity of solution-free sets of integers for general linear equations
Title not available (Why is that?)
Horn representation of a concept lattice
Counting Constraint Satisfaction Problems.
A new fixed point approach for stable networks and stable marriages

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)