A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
From MaRDI portal
Abstract: We give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal network reliability problem, which is to determine the probability that, in a undirected graph, assuming each edge fails independently, the remaining graph is still connected. Our main contribution is to confirm a conjecture by Gorodezky and Pak (Random Struct. Algorithms, 2014), that the expected running time of the "cluster-popping" algorithm in bi-directed graphs is bounded by a polynomial in the size of the input.
Recommendations
- scientific article; zbMATH DE number 7375995
- A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
- scientific article; zbMATH DE number 1263176
- An Algorithm for Network Reliability Bounds
- Computing Network Reliability in Time Polynomial in the Number of Cuts
- scientific article; zbMATH DE number 4045097
- scientific article; zbMATH DE number 4019092
Cites work
- scientific article; zbMATH DE number 420868 (Why is no real title available?)
- scientific article; zbMATH DE number 437298 (Why is no real title available?)
- scientific article; zbMATH DE number 1256746 (Why is no real title available?)
- scientific article; zbMATH DE number 1369835 (Why is no real title available?)
- scientific article; zbMATH DE number 7375995 (Why is no real title available?)
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
- A constructive proof of the general Lovász local lemma
- Approximating the Permanent
- Calculating bounds on reachability and connectedness in stochastic networks
- Complexity of network reliability computations
- Computational Complexity of Network Reliability Analysis: An Overview
- Computing rooted communication reliability in an almost acyclic digraph
- Generalized loop-erased random walks and approximate reachability
- Generating a random sink-free orientation in quadratic time
- Hodge theory for combinatorial geometries
- Improved bounds and algorithms for graph cuts and network reliability
- Inapproximability of the Tutte polynomial
- Log-concavity of characteristic polynomials and the Bergman fan of matroids
- Monte-Carlo algorithms for the planar multiterminal network reliability problem
- On a problem of Spencer
- On the computational complexity of the Jones and Tutte polynomials
- Polynomial-Time Approximation Algorithms for the Ising Model
- Proceedings of the 43rd annual ACM symposium on theory of computing, STOC '11. San Jose, CA, USA, June 6--8, 2011.
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- The Complexity of Enumeration and Reliability Problems
- The Computational Complexity of the Tutte Plane: the Bipartite Case
- The f-vector of a representable-matroid complex is log-concave
- The complexity of computing the sign of the Tutte polynomial
- Uniform sampling through the Lovász local lemma
Cited in
(22)- A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
- Counting hypergraph colorings in the local lemma regime
- New approximations for network reliability
- Sequential importance sampling algorithms for estimating the all-terminal reliability polynomial of sparse graphs
- Polynomial-time algorithms for multimarginal optimal transport problems with structure
- Parameter estimation for Gibbs distributions
- Tight bounds for popping algorithms
- Perfect sampling from spatial mixing
- Log-concave poset inequalities
- Fundamentals of partial rejection sampling
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
- scientific article; zbMATH DE number 7375995 (Why is no real title available?)
- The exponential time complexity of computing the probability that a graph is connected
- Optimally reconnecting graphs against an edge-destroying adversary
- Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
- Approximately counting bases of bicircular matroids
- scientific article; zbMATH DE number 1490110 (Why is no real title available?)
- Dynamic Sampling from Graphical Models
- Approximating queries on probabilistic graphs
- An FPRAS for two terminal reliability in directed acyclic graphs
- Near-linear time samplers for matroid independent sets with applications
- Conjunctive queries on probabilistic graphs: the limits of approximability
This page was built for publication: A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232317)
