# Invulnerability of planar two-tree networks

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

3 Scopus Citations

## Detail(s)

Original language English 16-25 Theoretical Computer Science 767 24 Sep 2018 Published - 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)

[ RIS ] [ BibTeX ]

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 Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review