Invulnerability of planar two-tree networks

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

3 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)16-25
Journal / PublicationTheoretical Computer Science
Volume767
Online published24 Sept 2018
Publication statusPublished - 3 May 2019

Abstract

Let us model the network by an undirected graph G, in which each edge fails independently with probability∈ [0, 1], the all-terminal reliability of the network is the probability that the graph G remains connected and it is one of the important measure for the invulnerability of the network. Clearly, the all-terminal reliability can be written as a polynomial in either q. Theoretically, it has been proved that calculating all-terminal reliability for planar networks is #-complete. Up now we cannot find any results for some special classes of the planar networks. This paper studies the all-terminal reliability of the two-tree networks and its generalizations. A linear algorithm for calculating the reliability of a planar two-tree networks is proposed, with algorithmic complexity (n), where n is the number of steps. Then both the uniformly-most reliable network model and the uniformly-worst reliable network model are determined by using the algorithm. Finally, a polynomial algorithm for planar two-connected networks is proposed based on an expended algorithm and the corresponding uniformly-most reliable network model and uniformly-worst reliable network model are also presented, with computational complexity (), where n is the number of steps.

Research Area(s)

  • Invulnerability, Planar network, Reliability, Uniformly-most model, Uniformly-worst model

Citation Format(s)

Invulnerability of planar two-tree networks. / Xiao, Yuzhi; Zhao, Haixing; Mao, Yaping et al.
In: Theoretical Computer Science, Vol. 767, 03.05.2019, p. 16-25.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review