An FPRAS for two terminal reliability in directed acyclic graphs
From MaRDI portal
Cites work
- #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
- A phase transition and a quadratic time unbiased estimator for network reliability
- A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
- A quasi-polynomial-time algorithm for sampling words from a context-free language
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
- A very hard log-space counting class
- Calculating bounds on reachability and connectedness in stochastic networks
- Complexity of network reliability computations
- Computational Complexity of Network Reliability Analysis: An Overview
- High-confidence estimation of small s-t reliabilities in directed acyclic networks
- Improved bounds and algorithms for graph cuts and network reliability
- Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests
- Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
- Modified log-Sobolev inequalities for strongly log-concave distributions
- Monte-Carlo algorithms for the planar multiterminal network reliability problem
- Monte-Carlo approximation algorithms for enumeration problems
- Random generation of combinatorial structures from a uniform distribution
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
- The Complexity of Enumeration and Reliability Problems
- The Complexity of Reliability Computations in Planar and Acyclic Graphs
- The relative complexity of approximate counting problems
- Tight bounds for popping algorithms
- Uniform sampling through the Lovász local lemma
This page was built for publication: An FPRAS for two terminal reliability in directed acyclic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875138)
