Advanced Search

Show simple item record

dc.contributor.authorAkram, Vahid Khalilpour
dc.contributor.authorUğurlu, Onur
dc.date.accessioned2022-02-15T16:57:17Z
dc.date.available2022-02-15T16:57:17Z
dc.date.issued2022
dc.identifier.issn1877-7503
dc.identifier.urihttps://doi.org/10.1016/j.jocs.2021.101518
dc.identifier.urihttps://hdl.handle.net/20.500.14034/73
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/?) and O(n2×logn) respectively, where ? 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. © 2021en_US
dc.language.isoengen_US
dc.publisherElsevier B.V.en_US
dc.relation.ispartofJournal of Computational Scienceen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectDistributed algorithmsen_US
dc.subjectLocalized algorithmsen_US
dc.subjectOptimizationen_US
dc.subjectVertex coveren_US
dc.subjectComputational complexityen_US
dc.subjectAverage coverageen_US
dc.subjectLocal neighborhoodsen_US
dc.subjectLocalized algorithmen_US
dc.subjectLocalized distributed algorithmen_US
dc.subjectMinimum vertex coveren_US
dc.subjectNeighborhood informationen_US
dc.subjectOptimisationsen_US
dc.subjectSubgraphsen_US
dc.subjectVertex coveren_US
dc.subjectVertex Cover problemsen_US
dc.subjectOptimizationen_US
dc.titleA localized distributed algorithm for vertex cover problemen_US
dc.typearticleen_US
dc.identifier.doi10.1016/j.jocs.2021.101518
dc.identifier.volume58en_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.authorscopusid55750051600
dc.authorscopusid55335002500
dc.identifier.scopus2-s2.0-85121273281en_US
dc.departmentBakırçay Üniversitesien_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record