Measuring the Survivability of a Network: Connectivity and Rest‐Connectivity
Manuel Duque-Antón, Frederic Bruyaux, Pierre Semal · European Transactions on Telecommunications · 2000
Abstract When evaluating the survivability performance of a communication network, it is important to detect whether the graph is connected, whether there are separation nodes and separation pairs. The algorithms [1] and [2] developed by Tar‐jan and Hopcroft are the adequate tools for this purpose. They are able to determine the bi‐ and triconnected components of a graph in o (N+E) where N is the number of nodes and E the number of edges of the graph. Practically however, the decomposition of the graph is a step only in the evaluation of the connectivity performance of a graph. Indeed, when a separation element (node or pair) has been detected, it is crucial to know what are the consequences if this element fails down. For example, which precise parts of the graph are disconnected or more simply how large are the parts which are separated by this element? The paper introduces the notion of rest‐connectivity. Basically, for each separation element, the rest‐connectivity value is defined as the number of node pairs which got disconnected by the failure of that separation element. In this paper, algorithms [1] and [2] are enhanced in order to determine the rest‐connectivity values for all separation nodes and pairs of a graph while keeping the complexity in o(N+E).