Monograph - 2020
 |
Monograph Information
Title
Safety and Reliability of Systems and Processes Summer Safety and Reliability Seminar 2020
Editors
Kołowrocki Krzysztof, Poland
Bogalecka Magdalena, Poland
Dąbrowska Ewa, Poland
Torbicki Mateusz, Poland
Publisher
Gdynia Maritime University, 2020
ISBN 978-83-7421-320-2 (printed)
e-ISBN 978-83-7421-321-9 (eBook)
DOI: 10.26408/srsp-2020
Language
English
Licence
|
A fast method for enumerating all minimal d-cut-sets in a flow network
MALINOWSKI Jacek 
Systems Research Institute, Polish Academy of Sciences, Warsaw, Poland, jacek.malinowski(at)ibspan.waw.pl
DOI: 10.26408/srsp-2020-13
ABSTRACT: 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-cut-set 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
F(
C) <
d or
F(
C) ≥
d.
C is the min-cut-set from which d-cut-sets are generated, and
F(
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 non-minimal 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.
KEYWORDS: flow network, component flow capacity, required flow, maximum flow, min-d-cut-set, min-cut-set

To cite this chapter:
Malinowski, J. 2020. A fast method for enumerating all minimal d-cut-sets in a flow network. In K. Kołowrocki et al. (Eds.), Safety and Reliability of Systems and Processes, Summer Safety and Reliability Seminar 2020. Gdynia Maritime University, Gdynia, 183-198, doi:10.26408/srsp-2020-13.