A heuristic algorithm to find rupture degree in graphs
Küçük Resim Yok
Tarih
2019
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Tubitak Scientific & Technological Research Council Turkey
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Since the problem of Konigsberg bridge was released in 1735, there have been many applications of graph theory in mathematics, physics, biology, computer science, and several fields of engineering. In particular, all communication networks can be modeled by graphs. The vulnerability is a concept that represents the reluctance of a network 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 graph G = (V, E) is an important graph vulnerability parameter and defined as r(G) = max{omega(G - S) - vertical bar S vertical bar - m(G - S) : omega(G - S) >= 2, S subset of V}, where omega(G - S) and m(G - S) denote the number of connected components and the size of the largest connected component in the graph G - S, respectively. Recently, it has been proved that finding the rupture degree problem is NP- complete. In this paper, a heuristic algorithm to determine the rupture degree of a graph has been developed. Extensive computational experience on 88 randomly generated graphs ranging from 20% to 90% densities and from 100 to 200 vertices shows that the proposed algorithm is very effective.
Açıklama
Anahtar Kelimeler
Network design and communication, graph vulnerability, connectivity, rupture degree, heuristic algorithm
Kaynak
Turkish Journal of Electrical Engineering and Computer Sciences
WoS Q Değeri
Q4
Scopus Q Değeri
Q3
Cilt
27
Sayı
5
