Computing Network Reliability in Time Polynomial in the Number of Cuts

DOI10.1287/OPRE.32.3.516MaRDI QIDQ3335484zbMATH OpenOpenAlexFDO

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

computing network reliabilityoperating pathpolynomial algorithmstochastic network

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

(25)

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

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)