A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
From MaRDI portal
Publication:4268894
DOI10.1137/S0097539796298340zbMath0937.05072OpenAlexW2014682451MaRDI QIDQ4268894
Publication date: 28 October 1999
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539796298340
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Reliability, availability, maintenance, inspection in operations research (90B25) Graph algorithms (graph-theoretic aspects) (05C85) Reliability, testing and fault tolerance of networks and computer systems (68M15) Connectivity (05C40)
Related Items
On Cutwidth Parameterized by Vertex Cover, Efficient algorithms for the problems of enumerating cuts by non-decreasing weights, Mixing of the Glauber dynamics for the ferromagnetic Potts model, Branch and bound for the cutwidth minimization problem, Sparse reliable graph backbones, Efficient Algorithms for the k Smallest Cuts Enumeration, Unnamed Item, On the algebraic complexity of some families of coloured Tutte polynomials, On cutwidth parameterized by vertex cover, Minimal cutwidth linear arrangements of abelian Cayley graphs, Graph parameters measuring neighbourhoods in graphs-bounds and applications, Generalized loop‐erased random walks and approximate reachability, Probabilistic verification and approximation, Scatter search for the cutwidth minimization problem, BOUNDARY-OPTIMAL TRIANGULATION FLOODING, Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time, A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability, A Variable Neighbourhood Search approach to the Cutwidth Minimization Problem, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, Fast Augmenting Paths by Random Sampling from Residual Graphs, On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)
