A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
From MaRDI portal
Publication:5232317
DOI10.1137/18M1201846zbMath1430.68441arXiv1709.08561OpenAlexW2949441583WikidataQ127887379 ScholiaQ127887379MaRDI QIDQ5232317
Publication date: 2 September 2019
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1709.08561
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Polynomial-time algorithms for multimarginal optimal transport problems with structure, Perfect sampling from spatial mixing, Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid, Counting Hypergraph Colorings in the Local Lemma Regime, Approximately counting bases of bicircular matroids, Dynamic Sampling from Graphical Models
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The \(f\)-vector of a representable-matroid complex is log-concave
- Inapproximability of the Tutte polynomial
- On a problem of Spencer
- Monte-Carlo algorithms for the planar multiterminal network reliability problem
- Hodge theory for combinatorial geometries
- Log-concavity of characteristic polynomials and the Bergman fan of matroids
- Proceedings of the forty-third annual ACM symposium on Theory of computing
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- Polynomial-Time Approximation Algorithms for the Ising Model
- Approximating the Permanent
- A constructive proof of the general lovász local lemma
- Calculating bounds on reachability and connectedness in stochastic networks
- Computational Complexity of Network Reliability Analysis: An Overview
- The Complexity of Enumeration and Reliability Problems
- Complexity of network reliability computations
- Computing rooted communication reliability in an almost acyclic digraph
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
- The Computational Complexity of the Tutte Plane: the Bipartite Case
- On the computational complexity of the Jones and Tutte polynomials
- Uniform sampling through the Lovasz local lemma
- The Complexity of Computing the Sign of the Tutte Polynomial
- Improved bounds and algorithms for graph cuts and network reliability
- Generalized loop‐erased random walks and approximate reachability
- Generating a random sink-free orientation in quadratic time
