Computing Network Reliability in Time Polynomial in the Number of Cuts

DOI10.1287/OPRE.32.3.516zbMATH Open0544.90034OpenAlexW2169621137MaRDI QIDQ3335484FDOQ3335484

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

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

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)

Cited In (23)

• A logic-based analysis of Dempster-Shafer theory
• Calculating bounds on reachability and connectedness in stochastic networks
• Approximate method to evaluate reliability of complex networks
• Spare routing problem with \(p\) minimal paths for time-based stochastic flow networks
• On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
• On enumerating minimal dicuts and strongly connected subgraphs
• A survey of efficient reliability computation using disjoint products approach
• Chance-constrained optimization of reliable fixed broadband wireless networks
• Enumerating disjunctions and conjunctions of paths and cuts in reliability theory
• Title not available (Why is that?)
• A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
• The exponential time complexity of computing the probability that a graph is connected
• A sum of disjoint products algorithm for reliability evaluation of flow networks
• Analysis and synthesis problems for network resilience
• A tool for computing computer network reliability
• Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time
• Combinatorial aspects of network reliability
• Nested Graphs
• An algorithm for network dimensioning under reliability considerations
• A note on the recognition of nested graphs
• Title not available (Why is that?)
• Network reliability: Numbers or insight? (A discussion paper)
• 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)