A fast method for enumerating all minimal d-cut-sets in a flow network

• Autorzy: Malinowski Jacek

Identyfikatory

DOI

10.26408/srsp-2020-13

• Konferencja: 14th Summer Safety & Reliability Seminars - SSARS 2020, 26-30 September 2020, Ciechocinek, Poland
• Języki publikacji: EN

Abstrakty

EN

A d-cut-set in a flow network is a set of components whose removal or blockage causes the maximum flow (MF) to fall below value d, provided that in fully operational network MF is greater or equal to d. A min-d-cutset is a d-cut set such that it does not contain any other d-cut-set. In turn, a cut-set is a set of components whose removal disconnects the source and the sink, which results in MF being equal to 0. A min-cut-set contains no other cut-set. The method works as follows: the min-cut-sets are ordered according to increasing flow capacities, then from every min-cut-set a number of d-cut-sets are generated and each of them is checked for being minimal and unique. The method features two different algorithms respectively applied if Φ(C) < 2d or Φ(C) ≥ 2d. C is the min-cut-set from which d-cut-sets are generated, and Φ(C) is the flow capacity of C. This distinction results in quick generation of min-d-cut-sets without finding many non-d-cut-sets or nonminimal d-cut-sets. Compared to the similar methods, the new one is highly efficient, due to several original solutions, e.g. an efficient method of checking the redundancy of candidates for min-d-cut-sets. Min-d-cut-sets have two main applications. First, they can be used to compute various reliability characteristics of flow networks. Second, the knowledge of these sets facilitates or even enables management and maintenance of various flow networks such as data transmission, water, power supply, or traffic networks, field drainage systems, etc.

Słowa kluczowe

EN

flow network; component flow capacity; required flow; maximum flow; min-d-cut-set; min-cut-set

• Wydawca: Gdynia Maritime University ; Polskie Towarzystwo Bezpieczeństwa i Niezawodności
• Czasopismo: Safety and Reliability of Systems and Processes
• Rocznik: 2020
• Tom: Summer Safety and Reliability Seminar 2020
• Strony: 183--198
• Opis fizyczny: Bibliogr. 13 poz., rys., tab.

Twórcy

autor

Malinowski Jacek

• Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland

• https://orcid.org/0000-0002-4413-1868

Bibliografia

• [1] Abel, U. & Bicker, R. 1982. Determination of all minimal cut-sets between a vertex pair in an undirected graph, IEEE Transactions on Reliability (31), 167-171.
• [2] Chakraborty, S. & Goyal, N. K. 2015. Irredundant subset cut enumeration for reliability evaluation of flow networks. IEEE Transactions on Reliability 64(4), 1194-1202.
• [3] Chakraborty, S. & Goyal, N. K. 2017. An efficient reliability evaluation approach for networks with simultaneous Multiple-Node-Pair flow requirements. Quality and Reliability Engineering International 33(5), 1067-1082.
• [4] Chatelet, E. et al. 1999. An optimal procedure to generate sums of disjoint products. Reliability Engineering and System Safety 65(3), 289-294.
• [5] Chaturvedi, S. K. 2007. Irredundant subset cut generation to compute capacity related reliability. International Journal of Performability Engineering 3(2), 243-256.
• [6] Cormen, T. H. et al. 2009. Introduction to Algorithms. MIT Press, London.
• [7] Malinowski, J. 2015. A new efficient algorithm generating all minimal s-t cut sets in a graphmodeled network. Proceedings of the International Conference of Numerical Analysis and Applied Mathematics, AIP Conference Proceedings, 480030-1-480030-4.
• [8] Malinowski, J. 2016. A fast tree-scanning algorithm finding a compact expression for the structure function of a system with known minimal path(cut) sets. Proceedings of the 26th European Safety and Reliability Conference, ESREL 2016, In: Risk, Reliability and Safety: Innovating Theory and Practice 1375-1379.
• [9] Niu, Y. F. et al. 2017. A new efficient algorithm for finding all d-minimal cuts in multi-state networks. Reliability Engineering and System Safety 166, 151-163.
• [10] Singh, B. 1994. Enumeration of node cut sets for an s–t network. Microelectronics Reliability 34, 559-561.
• [11] Soh, S. & Rai, S. 2005. An efficient cutset approach for evaluating communication-network reliability with heterogeneous link-capacities. IEEE Transactions on Reliability 54(1), 133-144.
• [12] Yeh, W. C. 2006. A simple algorithm to search for all MCs in networks. European Journal of Operational Research 174, 1694-1705.
• [13] Yeh, W. C. 2007. An improved sum-of-disjointproducts technique for the symbolic network reliability analysis with known minimal paths. Reliability Engineering and System Safety 92(2), 260-268.