A new robust approach to solve minimum vertex cover problem: Malatya vertex-cover algorithm

Basit Öğe Kaydı
dc.authoridOztemiz, Furkan/0000-0001-5425-3474
dc.authoridKarci, Ali/0000-0002-8489-8617
dc.authoridYakut, Selman/0000-0002-0649-1993
dc.authorwosidOztemiz, Furkan/KOD-2246-2024
dc.authorwosidKarci, Ali/AAG-5337-2019
dc.contributor.authorYakut, Selman
dc.contributor.authorOeztemiz, Furkan
dc.contributor.authorKarci, Ali
dc.date.accessioned2024-08-04T20:53:46Z
dc.date.available2024-08-04T20:53:46Z
dc.date.issued2023
dc.departmentİnönü Üniversitesien_US
dc.description.abstractThe 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 (psi) 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.en_US
dc.identifier.doi10.1007/s11227-023-05397-8
dc.identifier.endpage19769en_US
dc.identifier.issn0920-8542
dc.identifier.issn1573-0484
dc.identifier.issue17en_US
dc.identifier.scopus2-s2.0-85161298917en_US
dc.identifier.scopusqualityQ2en_US
dc.identifier.startpage19746en_US
dc.identifier.urihttps://doi.org/10.1007/s11227-023-05397-8
dc.identifier.urihttps://hdl.handle.net/11616/101389
dc.identifier.volume79en_US
dc.identifier.wosWOS:000999942400001en_US
dc.identifier.wosqualityQ2en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.language.isoenen_US
dc.publisherSpringeren_US
dc.relation.ispartofJournal of Supercomputingen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectMinimum vertex-coveren_US
dc.subjectGraph theoryen_US
dc.subjectMalatya centrality algorithmen_US
dc.subjectMalatya vertex-cover algorithmen_US
dc.subjectCentrality algorithmen_US
dc.titleA new robust approach to solve minimum vertex cover problem: Malatya vertex-cover algorithmen_US
dc.typeArticleen_US

Dosyalar

Koleksiyon

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