Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
On Parallel Calculation of All-Terminal Network Reliability. / Sergeev, Kirill; Migov, Denis.
Proceedings - 2021 17th International Asian School-Seminar "Optimization Problems of Complex Systems", OPCS 2021. Institute of Electrical and Electronics Engineers Inc., 2021. p. 104-107 (Proceedings - 2021 17th International Asian School-Seminar "Optimization Problems of Complex Systems", OPCS 2021).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - On Parallel Calculation of All-Terminal Network Reliability
AU - Sergeev, Kirill
AU - Migov, Denis
N1 - Funding Information: ACKNOWLEDGMENT The reported study was funded by RFBR and NSFC, project number 21-57-53011. Publisher Copyright: © 2021 IEEE
PY - 2021
Y1 - 2021
N2 - The paper presents parallel algorithms for calculating the exact value of all-terminal reliability of a network with unreliable edges and absolutely reliable nodes. A random graph is used as a model of such network. The algorithms are based on the factorization procedure which is a well-known sequential method of a reliability calculation. Parallelization of the algorithms consists in sending subgraphs, arising during the factorization of a network on the master process, to the rest of the processes that perform sequential calculation by the factorization. The basic idea of the parallel algorithms proposed is to distinguish those subgraphs, arising during the factorization in the work processes, that are relatively hard for reliability calculation. These subgraphs are sent back to the master process, which runs the computation of their reliability in a recursive way, i.e. according to the same scheme as with an initial graph. The results of the numerical experiments are given.
AB - The paper presents parallel algorithms for calculating the exact value of all-terminal reliability of a network with unreliable edges and absolutely reliable nodes. A random graph is used as a model of such network. The algorithms are based on the factorization procedure which is a well-known sequential method of a reliability calculation. Parallelization of the algorithms consists in sending subgraphs, arising during the factorization of a network on the master process, to the rest of the processes that perform sequential calculation by the factorization. The basic idea of the parallel algorithms proposed is to distinguish those subgraphs, arising during the factorization in the work processes, that are relatively hard for reliability calculation. These subgraphs are sent back to the master process, which runs the computation of their reliability in a recursive way, i.e. according to the same scheme as with an initial graph. The results of the numerical experiments are given.
KW - connectivity
KW - factoring method
KW - network reduction
KW - Network reliability
KW - parallel algorithm
KW - random graph
UR - http://www.scopus.com/inward/record.url?scp=85126952599&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/fdb3d918-dbec-37c3-b7b1-40a34f00fe9e/
U2 - 10.1109/OPCS53376.2021.9588720
DO - 10.1109/OPCS53376.2021.9588720
M3 - Conference contribution
AN - SCOPUS:85126952599
SN - 9781665405621
T3 - Proceedings - 2021 17th International Asian School-Seminar "Optimization Problems of Complex Systems", OPCS 2021
SP - 104
EP - 107
BT - Proceedings - 2021 17th International Asian School-Seminar "Optimization Problems of Complex Systems", OPCS 2021
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 17th International Asian School-Seminar "Optimization Problems of Complex Systems", OPCS 2021
Y2 - 13 September 2021 through 17 September 2021
ER -
ID: 35770428