On Parallel Calculation of All-Terminal Network Reliability

Kirill Sergeev, Denis Migov

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationProceedings - 2021 17th International Asian School-Seminar "Optimization Problems of Complex Systems", OPCS 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages104-107
Number of pages4
ISBN (Electronic)978-1-6654-0562-1
DOIs
Publication statusPublished - 2021
Event17th International Asian School-Seminar "Optimization Problems of Complex Systems", OPCS 2021 - Moscow, Russian Federation
Duration: 13 Sep 202117 Sep 2021

Publication series

NameProceedings - 2021 17th International Asian School-Seminar "Optimization Problems of Complex Systems", OPCS 2021

Conference

Conference17th International Asian School-Seminar "Optimization Problems of Complex Systems", OPCS 2021
CountryRussian Federation
CityMoscow
Period13.09.202117.09.2021

Keywords

  • connectivity
  • factoring method
  • network reduction
  • Network reliability
  • parallel algorithm
  • random graph

OECD FOS+WOS

  • 1.01 MATHEMATICS

Fingerprint

Dive into the research topics of 'On Parallel Calculation of All-Terminal Network Reliability'. Together they form a unique fingerprint.

Cite this