Computing Network Reliability in Time Polynomial in the Number of Cuts

DOI10.1287/OPRE.32.3.516MaRDI QIDQ3335484zbMATHOpenAlexFDO

Authors J. Scott Provan, Michael O. Ball

Publication date 1984

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/opre.32.3.516

zbMATH Keywords

polynomial algorithmstochastic networkcomputing network reliabilityoperating path

Mathematics Subject Classification ID

Reliability and life testing (62N05) Analysis of algorithms and problem complexity (68Q25) Reliability, availability, maintenance, inspection in operations research (90B25)

Recommendations

• scientific article; zbMATH DE number 4045097
• Reliability Computations for Planar Networks
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• Calculating bounds on reachability and connectedness in stochastic networks
• scientific article; zbMATH DE number 4097115

Cited in

(23)

• scientific article; zbMATH DE number 7375995 (Why is no real title available?)
• Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
• A logic-based analysis of Dempster-Shafer theory
• On enumerating minimal dicuts and strongly connected subgraphs
• A survey of efficient reliability computation using disjoint products approach
• Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions
• An algorithm for network dimensioning under reliability considerations
• Calculating bounds on reachability and connectedness in stochastic networks
• Approximate method to evaluate reliability of complex networks
• scientific article; zbMATH DE number 4045097 (Why is no real title available?)
• Chance-constrained optimization of reliable fixed broadband wireless networks
• A sum of disjoint products algorithm for reliability evaluation of flow networks
• Analysis and synthesis problems for network resilience
• Network reliability: Numbers or insight? (A discussion paper)
• Enumerating disjunctions and conjunctions of paths and cuts in reliability theory
• On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
• Nested Graphs
• A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
• A tool for computing computer network reliability
• Combinatorial aspects of network reliability
• Spare routing problem with \(p\) minimal paths for time-based stochastic flow networks
• The exponential time complexity of computing the probability that a graph is connected
• A note on the recognition of nested graphs

This page was built for publication: Computing Network Reliability in Time Polynomial in the Number of Cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3335484)