A localized distributed algorithm for vertex cover problem
Üst veriTüm öğe kaydını göster
Finding 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. © 2021
KaynakJournal of Computational Science
Başlık, yazar, küratör ve konuya göre gösterilen ilgili öğeler.
Ensemble of metaheuristics for energy-efficient hybrid flowshops: Makespan versus total energy consumption Öztop, Hande; Taşgetiren, M. Fatih; Kandiller, Levent; Eliiyi, Deniz Türsel; Gao, Liang (Elsevier, 2020)Due to its practical relevance, the hybrid flowshop scheduling problem (HFSP) has been widely studied in the literature with the objectives related to production efficiency. However, studies regarding energy consumption ...
Öztop, Hande; Taşgetiren, M. Fatih; Eliiyi, Deniz Türsel; Pan, Quan-Ke; Kandiller, Levent (Pergamon-Elsevier Science Ltd, 2020)The permutation flowshop scheduling problem (PFSP) has been extensively explored in scheduling literature because it has many real-world industrial implementations. In some studies, multiple objectives related to production ...
Crow Search Algorithm (CROW) is one of the members of recently developed swarm-based meta-heuristic algorithms. Literature includes different applications of this algorithm on engineering design problems. However, this ...