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

Cited in

(only showing first 100 items - show all)

Hard Enumeration Problems in Geometry and Combinatorics
Counting the number of vertex covers in a trapezoid graph
A graph polynomial for independent sets of bipartite graphs
Reliable assignments of processors to tasks and factoring on matroids
The distributed program reliability analysis on ring-type topologies
Counting and sampling minimum cuts in genus \(g\) graphs
Neighborhood conditions for graphs to be super restricted edge connected
The computational complexity of probabilistic inference using Bayesian belief networks
Connectivity of finite anisotropic random graphs and directed graphs
A proof of an inequality concerning \(k\)-restricted edge connectivity
The complexity of approximately counting stable roommate assignments
Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
On the hardness of approximate reasoning
\(\lambda ^{\prime}\)-optimal digraphs
Lower bounds on two-terminal network reliability
End-to-end availability-dependent pricing of network services
Edge cuts leaving components of order at least \(m\)
Understanding the generalized median stable matchings
Counting maximal independent sets in directed path graphs
The cross-entropy method for network reliability estimation
Approximation algorithm for estimating failure probability of multipath transmission
On optimally-\(\lambda^{(3)}\) transitive graphs
The computational complexity of the reliability problem on distributed systems
Network flow and 2-satisfiability
The homotopy classes of continuous maps between some nonmetrizable manifolds
The complexity of counting locally maximal satisfying assignments of Boolean CSPs
Counting the number of independent sets in chordal graphs
Fair cost allocations under conflicts - a game-theoretic point of view -
On optimizing edge connectivity of product graphs
Resource-constrained project scheduling: Notation, classification, models, and methods
Counting linear extensions
Counting independent sets in tricyclic graphs
The average reliability of a graph
Towards a dichotomy theorem for the counting constraint satisfaction problem
Super restricted edge connectivity of regular graphs
Reliability of task graph schedules with transient and fail-stop failures: complexity and algorithms
Dichotomy results for fixed point counting in Boolean dynamical systems
The complexity of approximately counting stable matchings
An application of the planar separator theorem to counting problems
A bound on 4-restricted edge connectivity of graphs
An analysis of Monte Carlo algorithms for counting problems
Counting almost minimum cutsets with reliability applications
Fast and simple algorithms to count the number of vertex covers in an interval graph
On super restricted edge connectivity of half vertex transitive graphs
Subtractive reductions and complete problems for counting complexity classes
Generalized loop-erased random walks and approximate reachability
Edge-packings of graphs and network reliability
On maximal 3-restricted edge connectivity and reliability analysis of hypercube networks
Finding a Level Ideal of a Poset
A dichotomy in the complexity of counting database repairs
Search for all \(d\)-mincuts of a limited-flow network
Independent sets from an algebraic perspective
Balancing \(U\)-lines in a multiple \(U\)-line facility
Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization
Counting Small Induced Subgraphs Satisfying Monotone Properties
Topological optimization of reliable networks under dependent failures
Counting solutions to binomial complete intersections
Enumeration aspects of maximal cliques and bicliques
Counting \(4 \times 4\) matrix partitions of graphs
Queries and materialized views on probabilistic databases
The maximum clique problem
Complexity issues for the sandwich homogeneous set problem
On the computational complexity of the Jones and Tutte polynomials
On the generation of circuits and minimal forbidden sets
High-confidence estimation of small \(s-t\) reliabilities in directed acyclic networks
On the complexity of dynamic programming for sequencing problems with precedence constraints
Restricted connectivity for some interconnection networks
Counting and enumerating preferred database repairs
Closest pair and the post office problem for stochastic points
Consecutive-2 systems on trees
Complexity of model checking for reaction systems
Probabilistic query answering over inconsistent databases
On 3-restricted edge connectivity of undirected binary Kautz graphs
An algorithm to generate the ideals of a partial order
Fast computation of bounds for two-terminal network reliability
Fast sequential importance sampling to estimate the graph reliability polynomial
Computing on binary strings
Counting independent sets in a tolerance graph
On the characterization of the domination of a diameter-constrained network reliability model
Horn representation of a concept lattice
On measuring inconsistency in definite and indefinite databases with denial constraints
Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
Information enhancement -- a tool for approximate representation of optimal strategies from influence diagrams
A new fixed point approach for stable networks and stable marriages
On the Tractability of SHAP Explanations
Computing the matching and independence polynomials of double hexagonal chains
Exact solutions in low-rank approximation with zeros
scientific article; zbMATH DE number 7375995 (Why is no real title available?)
The complexity of counting homeomorphs
Faster exponential-time algorithms for approximately counting independent sets
The complexity of approximating the complex-valued Potts model
Approximately counting independent sets in bipartite graphs via graph containers
Counting independent sets in graphs with bounded bipartite pathwidth
Invulnerability of planar two-tree networks
Network reliability: Heading out on the highway
On the reliability estimation of stochastic binary systems
The complexity of solution-free sets of integers for general linear equations
Graph theoretic characterization and reliability of the multiple-clique network
A logic-based analysis of Dempster-Shafer theory
A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases

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)