New advantages of using chains in computing multiple s − t Probabilistic connectivity

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

3 Citations (Scopus)

Abstract

We consider the problem of a network reliability calculation for a network with unreliable communication links and perfectly reliable nodes. For such networks, we study two different reliability indices: network average pairwise connectivity and average size of a connected subgraph that contains some special vertex. The problem of precise calculation of both these characteristics is known to be NP-hard. Both indices may be calculated or estimated through complete or partial enumeration of pairs of vertexes and calculation of their pairwise reliability. Methods for speeding up this process in the case when there are chains in a graph structure are presented in the paper.

Original languageEnglish
Title of host publicationComputational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings
EditorsBeniamino Murgante, Sanjay Misra, Carmelo M. Torre, Ana Maria A.C. Rocha, Shangguang Wang, Osvaldo Gervasi, Elena Stankova, Bernady O. Apduhan, David Taniar
PublisherSpringer-Verlag GmbH and Co. KG
Pages117-128
Number of pages12
ISBN (Print)9783319421070
DOIs
Publication statusPublished - 2016
Externally publishedYes
Event16th International Conference on Computational Science and Its Applications, ICCSA 2016 - Beijing, China
Duration: 4 Jul 20167 Jul 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9787
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Computational Science and Its Applications, ICCSA 2016
CountryChina
CityBeijing
Period04.07.201607.07.2016

Keywords

  • Algorithm
  • Network reliability
  • Pairwise connectivity
  • Random graph

Fingerprint

Dive into the research topics of 'New advantages of using chains in computing multiple s − t Probabilistic connectivity'. Together they form a unique fingerprint.

Cite this