A localized distributed algorithm for vertex cover problem

Basit Öğe Kaydı
dc.authoridUgurlu, Onur/0000-0003-2743-5939
dc.contributor.authorAkram, Vahid Khalilpour
dc.contributor.authorUgurlu, Onur
dc.date.accessioned2024-03-09T18:48:21Z
dc.date.available2024-03-09T18:48:21Z
dc.date.issued2022
dc.departmentİzmir Bakırçay Üniversitesien_US
dc.description.abstractFinding the minimum vertex cover of a given graph is a well-known NP-Hard problem that has many applications in various fields. In this paper, we propose a distributed localized algorithm for detecting vertex cover using 2-hop local neighborhood information in the distributed systems. We propose a scoring based policy and add the 1-hop neighbors of nodes with the highest score among their 2-hop neighbors to the vertex cover. The score of nodes is calculated by dividing the number of uncovered edges in their local subgraph by the number of their 1-hop neighbors. In this way, the score of each node determines the average coverage ratio by each neighbor of that node. The time and bit complexities of the proposed algorithm are O(n/Delta) and O(n(2) x log n) respectively, where Delta is the maximum node degree and n is the number of nodes. The comprehensive simulation results showed that the proposed algorithm could find up to 11% smaller solutions than the existing distributed algorithms with less than 1% difference of optimum solutions in most of the evaluated graphs.en_US
dc.identifier.doi10.1016/j.jocs.2021.101518
dc.identifier.issn1877-7503
dc.identifier.issn1877-7511
dc.identifier.scopus2-s2.0-85121273281en_US
dc.identifier.scopusqualityQ1en_US
dc.identifier.urihttps://doi.org/10.1016/j.jocs.2021.101518
dc.identifier.urihttps://hdl.handle.net/20.500.14034/1306
dc.identifier.volume58en_US
dc.identifier.wosWOS:000820278700003en_US
dc.identifier.wosqualityQ2en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.language.isoenen_US
dc.publisherElsevieren_US
dc.relation.ispartofJournal of Computational Scienceen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectDistributed Algorithms; Vertex Cover; Localized Algorithms; Optimizationen_US
dc.titleA localized distributed algorithm for vertex cover problemen_US
dc.typeArticleen_US

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
İsim:
1306.pdf
Boyut:
1.62 MB
Biçim:
Adobe Portable Document Format
İndir

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu