Computing Network Reliability in Time Polynomial in the Number of Cuts

DOI10.1287/opre.32.3.516zbMath0544.90034OpenAlexW2169621137MaRDI QIDQ3335484

Michael O. Ball, J. Scott Provan

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

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

Related Items

Enumerating disjunctions and conjunctions of paths and cuts in reliability theory, A survey of efficient reliability computation using disjoint products approach, Chance-Constrained Optimization of Reliable Fixed Broadband Wireless Networks, On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts, A logic-based analysis of Dempster-Shafer theory, Approximate method to evaluate reliability of complex networks, Combinatorial aspects of network reliability, Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions, On enumerating minimal dicuts and strongly connected subgraphs, An algorithm for network dimensioning under reliability considerations, Spare routing problem with \(p\) minimal paths for time-based stochastic flow networks, A sum of disjoint products algorithm for reliability evaluation of flow networks, Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time, A Note on the Recognition of Nested Graphs, Analysis and synthesis problems for network resilience, Nested Graphs, Network reliability: Numbers or insight? (A discussion paper)