Akademik Veri Yönetim Sistemi
JOURNAL OF SUPERCOMPUTING, cilt.1, ss.1-24, 2023 (SCI-Expanded)
The minimum vertex-cover problem (MVCP) is an NP-complete optimization problem widely used in areas such as graph theory, social network, security and transportation, etc. Different approaches and algorithms have been proposed in the literature to solve this problem, since MVCP is an optimization problem, the solutions developed for this problem could be more intuitive and give results under certain constraints. In addition, the proposed solution methods for this problem could be more effective, and the determined solution sets change in each iteration. The algorithms/methods developed for solving MVCP are mostly based on heuristic or greedy approaches. This study presents the Malatya vertex-cover algorithm, which provides an efficient solution and a robust approach based on the Malatya centrality value algorithm for MVCP. Although MVCP is an NP-complete problem that cannot be solved in polynomial time, the proposed method offers a polynomial solution to this problem, and the obtained solutions are optimum or near-optimum (optimal solution). This algorithm consists of two basic steps. In the first step, the Malatya centrality values of the nodes in the graph are calculated using the Malatya centrality algorithm. The Malatya centrality value of the nodes in any graph is the summation of the ratio of the node’s degree to the adjacent nodes’ degrees for each node. In the second step, nodes are selected for the MVCP solution based on the node with the maximum Malatya centrality value (Ψ) in the graph is selected and added to the solution set. Then this node and the edges incident on this node are removed from the graph. For the graph consisting of the remaining nodes, Malatya centrality values are calculated again, and the selection process is continued. The process is terminated when all edges in the graph are covered. The proposed algorithm has been tested on artificial, actual graphs and large-scale random graphs produced with the Erdos–Renyi model. When the results are examined, the proposed algorithm yields a robust solution set in polynomial time and polynomial space independent of constraints. In addition, the successful test results in the sample graphs and the analysis of the proposed approach show the effectiveness/superiority of the Malatya centrality algorithm and the proposed method.