Complexity of network reliability computations
From MaRDI portal
Publication:3887194
DOI10.1002/net.3230100206zbMath0443.90038MaRDI QIDQ3887194
Publication date: 1980
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230100206
computational complexity; NP-hard problems; directed networks; node failures; undirected networks; network reliability measures
68Q25: Analysis of algorithms and problem complexity
90B25: Reliability, availability, maintenance, inspection in operations research
90B10: Deterministic network models in operations research
Related Items
Bounds on the Reliability Polynomial for Shellable Independence Systems, \(\lambda ^{\prime}\)-optimal digraphs, Computational complexity of impact size estimation for spreading processes on networks, Connectivity, stability and efficiency in a network as an information flow, Edge-packings of graphs and network reliability, A factoring approach for the stochastic shortest path problem, Computing optimal assignments for residual network reliability, Super edge-connectivity of de Bruijn and Kautz undirected graphs, Bounds for coherent reliability structures, On super restricted edge connectivity of half vertex transitive graphs, Finding the probability of infection in an SIR network is NP-hard, An algorithm to compute the all-terminal reliability measure., On optimally-\(\lambda^{(3)}\) transitive graphs, Neighborhood conditions for graphs to be super restricted edge connected, System Reliability Analysis in the Presence of Dependent Component Failures, On super connectivity of Cartesian product graphs, Application of Markov chains for the reliability analysis of systems with a complex structure, Algebraic Methods Applied to Network Reliability Problems, Counting almost minimum cutsets with reliability applications, Structural questions with GERT-networks, Unnamed Item