A New Technique in Minimal Path and Cutset Evaluation (Q3690764)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3914256
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A New Technique in Minimal Path and Cutset Evaluation |
scientific article; zbMATH DE number 3914256 |
Statements
A New Technique in Minimal Path and Cutset Evaluation (English)
0 references
1985
0 references
reliability
0 references
computer implementation
0 references
enumeration
0 references
undirected network
0 references
failures
0 references
minimal cutsets
0 references
minimal paths
0 references
Fortran computer program
0 references
0.8691091537475586
0 references
0.8656922578811646
0 references
0.8325324058532715
0 references
Consider an undirected network of interconnected components with a single source and a single sink. The components are subject to failures, and the network is said to have failed if component failures disconnect the source from the sink. The problem is to determine all sets of components whose failure causes a network failure and that are minimal with respect to this property (minimal cutsets). Current methods construct the minimal cutsets from a list of simple paths between the source and the sink. It is implicitly contained in the minimal-path tree of the network, which describes all the interlinking connections of the components from the source to the sink. The contribution of the paper is to note that it is not necessary to consider all minimal paths when constructing the cutsets, but only a smallest subset of so-called basic minimal paths. These are defined as ''minimal paths in which no element of the path is linked to another by any branch in the network except with those elements before or after it in the path''. An algorithm is provided for constructing the minimal-path tree recursively in a way which makes the enumeration of basic paths simple. Next, the minimal cutsets are constructed in the usual manner, but from the list of basic paths instead of the full list of minimal paths. Methods of indirect addressing are proposed to make this computation more efficient. Examples are provided for constructing up to fourth-order cutsets. For a twelve-node network, the number of minimal paths is 150, while there are only 11 basic paths. The reduction for a twenty-node network is from over 2000 to 88 basic paths. No time comparison is made between the method of the paper and the current technique. A listing of the Fortran computer program that was used for the calculation is also provided.
0 references