Monte-Carlo algorithms for the planar multiterminal network reliability problem

DOI10.1016/0885-064X(85)90021-4zbMath0596.90033OpenAlexW2007746582MaRDI QIDQ1079111

Michael Luby, Richard M. Karp

Publication date: 1985

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0885-064x(85)90021-4

zbMATH Keywords

enumerationMonte-Carlo algorithmsfailure probability of a multiterminal planar network

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Applications of mathematical programming (90C90) Reliability, availability, maintenance, inspection in operations research (90B25)

Related Items (39)

Sixty years of network reliability ⋮ Monte-Carlo algorithms for the planar multiterminal network reliability problem ⋮ Random generation of combinatorial structures from a uniform distribution ⋮ Sequential Monte Carlo for counting vertex covers in general graphs ⋮ Unnamed Item ⋮ DNF sparsification and a faster deterministic counting algorithm ⋮ Approximate counting, uniform generation and rapidly mixing Markov chains ⋮ A mildly exponential approximation algorithm for the permanent ⋮ Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case ⋮ Network reliability: Heading out on the highway ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ An OpenCL implementation of a forward sampling algorithm for CP-logic ⋮ Unnamed Item ⋮ Recent developments in information-based complexity ⋮ An inequality for polymatroid functions and its applications. ⋮ Robust Estimation of the Mean with Bounded Relative Standard Deviation ⋮ On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions ⋮ Importance sampling the union of rare events with an application to power systems analysis ⋮ An introduction to randomized algorithms ⋮ Stochastic enumeration with importance sampling ⋮ Lower bounds for sampling algorithms for estimating the average ⋮ Approximately counting paths and cycles in a graph ⋮ Generalized loop‐erased random walks and approximate reachability ⋮ Approximating probabilistic inference in Bayesian belief networks is NP- hard ⋮ Probabilistic verification and approximation ⋮ Counting substrate cycles in topologically restricted metabolic networks ⋮ Computational complexity of impact size estimation for spreading processes on networks ⋮ Uniform generation in spatial constraint databases and applications ⋮ A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant ⋮ High-confidence estimation of small s -t reliabilities in directed acyclic networks ⋮ Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs ⋮ Approximability of the eight-vertex model ⋮ A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability ⋮ Consecutive-2 systems on trees ⋮ An analysis of Monte Carlo algorithm for estimating the permanent ⋮ Unnamed Item ⋮ Computational complexity of loss networks ⋮ Average case optimality ⋮ Balanced and Approximate Zero-Variance Recursive Estimators for the Network Reliability Problem

Cites Work

• Unnamed Item
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• The Complexity of Enumeration and Reliability Problems
• Sequential Destruction Method for Monte Carlo Evaluation of System Reliability
• Efficient Evaluation of System Reliability by Monte Carlo Method
• Network reliability analysis: Part I

This page was built for publication: Monte-Carlo algorithms for the planar multiterminal network reliability problem