Monograph


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


Previous chapter - Contents - Next chapter