Advanced search
Advanced search
Advanced search
Advanced search
Advanced search
Raport Badawczy = Research Report ; RB/8/2017
Instytut Badań Systemowych. Polska Akademia Nauk ; Systems Research Institute. Polish Academy of Sciences
32 pages ; 21 cm ; Bibliography p. 31-32
A new solution to the problem of finding all minimal d-cut-sets in a flow network with one source and one sink node is presented. According to the developed method, min-d-cut-sets are generated from min-τ-cut sets, where a τ-cut-set is a set of components whose removal or failure causes the source and sink to be topologically disconnected. A τ-cut-set is minimal if no its subset is a τ-cut-set. The method consists of two algorithms; the first one is applied if Φ(C)<2d, the second - if Φ(C)>=2d, where C is the min-τ-cut-set from which min-d-cut-sets are generated, and Φ(C) denotes the total flow capacity of C's components. This distinction results in quick generation of min-d-cut-sets without first having to find many non-d-cut sets or non-minimal d-cut-sets. The presented method is highly efficient, due to a number of technical improvements which include applying different algorithms for the cases Φ(C)<2d and Φ(C)>=2d, and an effective method of checking if the found min-d-cut set is a redundant one.
Raport Badawczy = Research Report
Creative Commons Attribution BY 4.0 license
Copyright-protected material. [CC BY 4.0] May be used within the scope specified in Creative Commons Attribution BY 4.0 license, full text available at: ; -
Systems Research Institute of the Polish Academy of Sciences
Library of Systems Research Institute PAS
Oct 19, 2021
Jan 13, 2020
47
https://rcin.org.pl./publication/115380
Edition name | Date |
---|---|
RB-2017-08 : Malinowski Jacek : A new efficient method of enumerating all min-d-cut-sets in a flow network | Oct 19, 2021 |
Malinowski, Jacek
Kiwiel, Krzysztof
Kiwiel, Krzysztof
Malinowski, Jacek
Malinowski, Jacek
Malinowski, Jacek
Malinowski, Jacek
Malinowski, Jacek