<abstract xmlns="http://www.w3.org/1999/xhtml">

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

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(G–S )–|S |–m(G–S ):S ⊂ V (G) and w(G–S )>1} where m(G–S ) is the order of a largest connected component in G–S and w(G–S ) is the number of components of G–S, 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

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

Pamukkale University, Faculty of Engineering

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

{"article-title":"On agglomeration-based rupture degree in networks and a heuristic algorithm"}

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....

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

Publié en ligne: 08 août 2023

Pages: 124 - 145

Reçu: 27 avr. 2023

DOI: https://doi.org/10.2478/ausi-2023-0010

Mots clés
graphs, network design and communication, complex networks, connectivity, vulnerability, rupture degree, agglomeration

© 2023 Muammer Ağtaş et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

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

Publié en ligne: 08 août 2023

Pages: 124 - 145

Reçu: 27 avr. 2023

DOI: https://doi.org/10.2478/ausi-2023-0010

Mots clésgraphs, network design and communication, complex networks, connectivity, vulnerability, rupture degree, agglomeration

© 2023 Muammer Ağtaş et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Mots clés
graphs, network design and communication, complex networks, connectivity, vulnerability, rupture degree, agglomeration