Tufan TURACI, Rafet DURGUT, Hakan KUTUCU

A heuristic algorithm to find rupture degree in graphs

Since the problem of Konigsberg bridge was released in 1735, there have been many applications ofgraph theory in mathematics, physics, biology, computer science, and several fields of engineering. In particular, allcommunication networks can be modeled by graphs. The vulnerability is a concept that represents the reluctance of anetwork to disruptions in communication after a deterioration of some processors or communication links. Furthermore,the vulnerability values can be computed with many graph theoretical parameters. The rupture degree r(G) of a graphG = (V, E) is an important graph vulnerability parameter and defined as r(G) = max{ω(G − S) − |S| − m(G − S) :ω(G − S) ≥ 2, S ⊂ V }, where ω(G − S) and m(G − S) denote the number of connected components and the size of thelargest connected component in the graph G − S , respectively. Recently, it has been proved that finding the rupturedegree problem is NP -complete. In this paper, a heuristic algorithm to determine the rupture degree of a graph has beendeveloped. Extensive computational experience on 88 randomly generated graphs ranging from 20% to 90% densitiesand from 100 to 200 vertices shows that the proposed algorithm is very effective.

PDF

___

[1] Mishkovski I, Biey M, Kocarev L. Vulnerability of complex networks. Communications in Nonlinear Science and Numerical Simulation 2011; 16 (1): 341-349. doi: 10.1016/j.cnsns.2010.03.018
[2] Durgut R, Turaci T, Kutucu H. Global distribution center number of some graphs and an algorithm. RAIROOperations Research 2018; In press. doi: 10.1051/ro/2018119
[3] Turaci T, Okten M. Vulnerability of mycielski graphs via residual closeness. Ars Combinatoria 2015; 118: 419-427.
[4] Frank H, Frisch IT. Analysis and design of survivable networks. IEEE Transactions on Communications Technology 1970; 18 (5): 501-519. doi: 10.1109/TCOM.1970.1090419
[5] Chvatal V. Tough graphs and hamiltonian circuits. Discrete Mathematics 1973; 5 (3): 215-228. doi: 10.1016/0012- 365X(73)90138-6
[6] Bagga KS, Beineke LW, Goddard WD, Lipman MJ, Pippert RE. A survey of integrity. Discrete Applied Mathematics 1992; 37-38: 13-28. doi: 10.1016/0166-218X(92)90122-Q
[7] Jung HA. On maximal circuits infinite graphs. Annals of Discrete Mathematics 1978; 3: 129-144. doi: 10.1016/S0167-5060(08)70503-X
[8] Li Y, Zhang S, Li X. Rupture degree of graphs. International Journal of Computer Mathematics 2005; 82 (7): 793-803. doi: 10.1080/00207160412331336062
[9] West BD. Introduction to Graph Theory. 2nd ed. Urbana, NJ, USA: Prentice Hall, 2001.
[10] Aslan E. Weak-rupture degree of graphs. International Journal of Foundations of Computer Science 2016; 27 (6): 725-738. doi: 10.1142/S0129054116500258
[11] Aslan E. Edge-rupture degree of a graph. Dynamics of Continuous, Discrete and Impulsive Systems Series B: Applications and Algorithms 2015; 22 (2): 155-161.
[12] Bacak B, Oz E. Neighbor rupture degree of transformation graphs. International Journal of Foundations of Computer Science 2017; 28 (4): 335-355. doi: 10.1142/S0129054117500216
[13] Kurkçu OK, Aslan E. A comparison between edge neighbor rupture degree and edge scattering number in graphs. International Journal of Foundations of Computer Science 2018; 29 (7): 1119-1142. doi: 10.1142/S0129054118500247
[14] Aytac V, Turaci T. Relationships between vertex attack tolerance and other vulnerability parameters. RAIRO - Theoretical Informatics and Applications 2017; 51 (1): 17-27. doi: 10.1051/ita/2017005
[15] Li F, Li X. Computing the rupture degrees of graphs. In: 7th International Symposium on Parallel Architectures, Algorithms and Networks; Hong Kong, China; 2004, pp. 368-373.
[16] Aytac A, Aksu H. Some results for the rupture degree. International Journal of Foundations of Computer Science 2013; 24 (8): 1329-1338. doi: 10.1142/S0129054113500366
[17] Aytac A, Aksu H. The rupture degree of some graphs. Mathematica Balkanica 2010; 24 (1-2): 85-101.
[18] Aytac A, Odabas ZN. Computing the rupture degree in composite graphs. International Journal of Foundations of Computer Science 2010; 21 (3): 311-319. doi: 10.1142/S012905411000726X
[19] Kirlangic A, Bacak-Turan G. On the rupture degree of a graph. Neural Network World 2012; 22 (1): 39-51. doi: 10.14311/NNW.2012.22.003
[20] Li Y. The rupture degree of trees. International Journal of Computer Mathematics 2008; 85 (11): 1629-1635. doi: 10.1080/00207160701553367
[21] Odabas ZN, Aytac A. Rupture degree and middle graphs. Comptes Rendus de Lacademie Bulgare des Sciences 2010; 65 (3): 315-322.
[22] Li F. Isolated rupture degree of trees and gear graphs. Neural Network World 2015; 25 (3): 287-300. doi: 10.14311/NNW.2015.25.015
[23] Berberler ME, Berberler ZN. Measuring the vulnerability in networks: a heuristic approach. Ars Combinatoria 2017; 135: 3-15.
[24] Cormen HT, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. 3rd ed. Cambridge, London, UK: The MIT Press, 2009.