A heuristic algorithm to find rupture degree in graphs

Basit Öğe Kaydı
dc.authoridKutucu, Hakan/0000-0001-7144-7246
dc.authoridTURACI, TUFAN/0000-0002-6159-0935
dc.authoridDurgut, Rafet/0000-0002-6891-5851
dc.contributor.authorDurgut, Rafet
dc.contributor.authorTuraci, Tufan
dc.contributor.authorKutucu, Hakan
dc.date.accessioned2024-09-29T16:08:19Z
dc.date.available2024-09-29T16:08:19Z
dc.date.issued2019
dc.departmentKarabük Üniversitesien_US
dc.description.abstractSince 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.en_US
dc.identifier.doi10.3906/elk-1903-29
dc.identifier.endpage3441en_US
dc.identifier.issn1300-0632
dc.identifier.issn1303-6203
dc.identifier.issue5en_US
dc.identifier.scopus2-s2.0-85072617554en_US
dc.identifier.scopusqualityQ3en_US
dc.identifier.startpage3433en_US
dc.identifier.trdizinid337425en_US
dc.identifier.urihttps://doi.org/10.3906/elk-1903-29
dc.identifier.urihttps://search.trdizin.gov.tr/tr/yayin/detay/337425
dc.identifier.urihttps://hdl.handle.net/20.500.14619/7493
dc.identifier.volume27en_US
dc.identifier.wosWOS:000486425400012en_US
dc.identifier.wosqualityQ4en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.indekslendigikaynakTR-Dizinen_US
dc.language.isoenen_US
dc.publisherTubitak Scientific & Technological Research Council Turkeyen_US
dc.relation.ispartofTurkish Journal of Electrical Engineering and Computer Sciencesen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectNetwork design and communicationen_US
dc.subjectgraph vulnerabilityen_US
dc.subjectconnectivityen_US
dc.subjectrupture degreeen_US
dc.subjectheuristic algorithmen_US
dc.titleA heuristic algorithm to find rupture degree in graphsen_US
dc.typeArticleen_US

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu
TR-Dizin İndeksli Yayınlar Koleksiyonu