On agglomeration-based rupture degree in networks and a heuristic algorithm
Muammer Ağtaş, Tufan Turacı · Acta Universitatis Sapientiae Informatica · 2023
Abstract The rupture degree is one the most important vulnerability parameter in networks which are modelled by graphs. LetG(V(G),E(G)) be a simple undirected graph. The rupture degree is defined byr(G) = max{w(G–S)–|S |–m(G–S):S ⊂ V(G) andw(G–S)>1}where m(G–S) is the order of a largest connected component inG–Sandw(G–S) is the number of components ofG–S, respectively. In this paper, we consider the vertex contraction method based on the network agglomeration operation for each vertex ofG. Then, we have presented two graph vulnerability parameters called byagglomeration rupture degreeandaverage lower agglomeration rupture degree. Furthermore, the exact values of them for some graph families are given. Finally, we proposed a polynomial time heuristic algorithm to obtain the values ofagglomeration rupture degreeandaverage