Accès libre

On agglomeration-based rupture degree in networks and a heuristic algorithm

À propos de cet article

Citez

The rupture degree is one the most important vulnerability parameter in networks which are modelled by graphs. Let G(V (G),E (G)) be a simple undirected graph. The rupture degree is defined by r(G) = max{w(GS )–|S |m(GS ):S ⊂ V (G) and w(GS )>1} where m(GS ) is the order of a largest connected component in GS and w(GS ) is the number of components of GS, respectively. In this paper, we consider the vertex contraction method based on the network agglomeration operation for each vertex of G. Then, we have presented two graph vulnerability parameters called by agglomeration rupture degree and average 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 of agglomeration rupture degree and average

eISSN:
2066-7760
Langue:
Anglais
Périodicité:
2 fois par an
Sujets de la revue:
Computer Sciences, other