Abstract
Network reliability is famous for its problem solving ability in several real-life applications. However, due to its NP-hard nature (Ball in IEEE Trans Reliab 35(3):230–238, 1986), researchers are devoted to the improvement of computational efficiency in various approaches. Although flow in networks depicts its combination properties, only few of them are useful in the calculation of network reliability. In some point of views, we call it mining in flow data. This paper presents techniques of how to efficiently do the flow data mining tasks. A skill based on backtrack and maximal flow is illustrated with examples and benchmarks. The results show that the proposed approach is valuable in the calculation of network reliability.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ball, M. O. (1986). Computational complexity of network reliability analysis: An overview. IEEE Transactions on Reliability, 35(3), 230–238.
Chen, S. G. (2014). Reduced recursive inclusion-exclusion principle for the probability of union events. In 2014 IEEE international conference on industrial engineering and engineering management (pp. 1–3). Malaysia: Selangor.
Chen, S. G. (2018). A novel approach to search for all solutions of a non-negative linear Diophantine equation. In 24th ISSAT international conference on reliability and quality in design (pp. 55–57).
Chen, S. G., & Lin, Y. K. (2012). Search for all minimal paths in a general large flow network. IEEE Transactions on Reliability, 61(4), 949–956.
Edmonds, J., & Karp, R. M. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2), 248–264.
Ford, L. R., & Fulkerson, D. R. (1962). Flows in networks. Princeton, NJ: Princeton University Press.
Forghani-elahabad, M., & Kagan, N. (2019). Reliability evaluation of a stochastic-flow network in terms of minimal paths with budget constraint. IISE Transactions, 51(5), 547–558.
Lin, J. S., Jane, C. C., & Yuan, J. (1995). On reliability evaluation of a capacitated-flow network in terms of minimal pathsets. Networks, 25, 131–138.
Lin, Y. K. (2001). A simple algorithm for reliability evaluation of a stochastic-flow network with node failure. Computers and Operations Research, 28(13), 1277–1285.
Lin, Y. K., & Chen, S. G. (2017a). A maximal flow method to search for \( d \)-MPs in stochastic-flow networks. Journal of Computational Science, 22, 119–125.
Lin, Y. K., & Chen, S. G. (2017b). A merge search approach to find minimal path vectors in multistate networks. International Journal of Reliability, Quality and Safety Engineering, 24(1), 1750,005–1–1750,005–12.
Lin, Y. K., & Chen, S. G. (2019). An efficient searching method for minimal path vectors in multi-state networks. Annals of Operations Research,. https://doi.org/10.1007/s10479-019-03158-6.
Schrijver, A. (2002). On the history of the transportation and maximum flow problems. Mathematical Programming, 91(3), 437–445.
Xu, X. Z., Niu, Y. F., & Li, Q. (2019). Efficient enumeration of-minimal paths in reliability evaluation of multistate networks. Complexity, 2019, 1–10.
Yeh, W., & Zuo, M. J. (2019). A new subtraction-based algorithm for the \(d\)-MPs for all d problem. IEEE Transactions on Reliability, 68(3), 999–1008.
Acknowledgements
This research is supported in part by the Ministry of Science and Technology, Taiwan, Republic of China, under Grant Nos. MOST 107-2221-E-236-004-MY3 and MOST 105-2221-E-009-188-MY3.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Lin, YK., Chen, SG. Reliability evaluation in terms of flow data mining for multistate networks. Ann Oper Res 311, 225–237 (2022). https://doi.org/10.1007/s10479-020-03774-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-020-03774-7