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. 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 connect...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Sciendo
2023-08-01
|
| Series: | Acta Universitatis Sapientiae: Informatica |
| Subjects: | |
| Online Access: | https://doi.org/10.2478/ausi-2023-0010 |
| _version_ | 1797743769405095936 |
|---|---|
| author | Ağtaş Muammer Turaci Tufan |
| author_facet | Ağtaş Muammer Turaci Tufan |
| author_sort | Ağtaş Muammer |
| collection | DOAJ |
| description | 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 |
| first_indexed | 2024-03-12T15:00:12Z |
| format | Article |
| id | doaj.art-265922b7fbd24ba1bffd7ad150b7d3e6 |
| institution | Directory Open Access Journal |
| issn | 2066-7760 |
| language | English |
| last_indexed | 2024-03-12T15:00:12Z |
| publishDate | 2023-08-01 |
| publisher | Sciendo |
| record_format | Article |
| series | Acta Universitatis Sapientiae: Informatica |
| spelling | doaj.art-265922b7fbd24ba1bffd7ad150b7d3e62023-08-14T07:10:15ZengSciendoActa Universitatis Sapientiae: Informatica2066-77602023-08-0115112414510.2478/ausi-2023-0010On agglomeration-based rupture degree in networks and a heuristic algorithmAğtaş Muammer0Turaci Tufan11Pamukkale University, Faculty of Engineering, Department of Computer Engineering, 20160Denizli, Turkey2Pamukkale University, Faculty of Engineering, Department of Computer Engineering, 20160Denizli, TurkeyThe 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 averagehttps://doi.org/10.2478/ausi-2023-0010graphsnetwork design and communicationcomplex networksconnectivityvulnerabilityrupture degreeagglomeration |
| spellingShingle | Ağtaş Muammer Turaci Tufan On agglomeration-based rupture degree in networks and a heuristic algorithm Acta Universitatis Sapientiae: Informatica graphs network design and communication complex networks connectivity vulnerability rupture degree agglomeration |
| title | On agglomeration-based rupture degree in networks and a heuristic algorithm |
| title_full | On agglomeration-based rupture degree in networks and a heuristic algorithm |
| title_fullStr | On agglomeration-based rupture degree in networks and a heuristic algorithm |
| title_full_unstemmed | On agglomeration-based rupture degree in networks and a heuristic algorithm |
| title_short | On agglomeration-based rupture degree in networks and a heuristic algorithm |
| title_sort | on agglomeration based rupture degree in networks and a heuristic algorithm |
| topic | graphs network design and communication complex networks connectivity vulnerability rupture degree agglomeration |
| url | https://doi.org/10.2478/ausi-2023-0010 |
| work_keys_str_mv | AT agtasmuammer onagglomerationbasedrupturedegreeinnetworksandaheuristicalgorithm AT turacitufan onagglomerationbasedrupturedegreeinnetworksandaheuristicalgorithm |