Graph structure is widely used to describe problems in different fields. Problems in many areas, such as security and transportation, are among them. The problems can be solved using approaches similar to the graph structure. The independent set problem, which is NPComplete problem, is one of the main problems of graph theory and is used in modeling many problems. The implementation of the Independent set problem with the most significant possible number of nodes in the graph is called the Maximum Independent set. A lot of algorithm approach are proposed to solve the problem. This study proposes an effective approach for the maximum independent problem. This approach occurs two steps: computing the Malatya centrality value and determining the maximum independent set. In the first step, centrality values are computed for the nodes forming the graph structure using the Malatya algorithm. The Malatya centrality value of the nodes in any graph is the sum of the ratios of the node's degree to the neighboring nodes' degrees. The second step is to determine the nodes to be selected for the maximum independent set problem. Here, the node with the minimum Malatya centrality value is selected and added to the independent set. Then, the edges of this node, its adjacent nodes, and the edges of adjacent nodes are subtracted from the graph. By repeating the new graph structure calculations, all vertexes are deleted so that the maximum independent set is determined. It is observed on the sample graph that the proposed approach provides an effecient solution for the maximum independent set. Successful test results and analyzes denonstrate the effectiveness of the proposed approach.
Maximum independent set Graph theory Malatya centrality algorithm Malatya centrality value.



Graph structure is widely used to describe problems in different fields. Problems in many areas, such as security and transportation, are among them. The problems can be solved using approaches similar to the graph structure. The independent set problem, which is NPComplete problem, is one of the main problems of graph theory and is used in modeling many problems. The implementation of the Independent set problem with the most significant possible number of nodes in the graph is called the Maximum Independent set. A lot of algorithm approach are proposed to solve the problem. This study proposes an effective approach for the maximum independent problem. This approach occurs two steps: computing the Malatya centrality value and determining the maximum independent set. In the first step, centrality values are computed for the nodes forming the graph structure using the Malatya algorithm. The Malatya centrality value of the nodes in any graph is the sum of the ratios of the node's degree to the neighboring nodes' degrees. The second step is to determine the nodes to be selected for the maximum independent set problem. Here, the node with the minimum Malatya centrality value is selected and added to the independent set. Then, the edges of this node, its adjacent nodes, and the edges of adjacent nodes are subtracted from the graph. By repeating the new graph structure calculations, all vertexes are deleted so that the maximum independent set is determined. It is observed on the sample graph that the proposed approach provides an effecient solution for the maximum independent set. Successful test results and analyzes denonstrate the effectiveness of the proposed approach.
Maximum independent set Graph theory Malatya centrality algorithm Malatya centrality value.

Birincil Dil  İngilizce 

Konular  Yazılım Mühendisliği, Yazılım Testi, Doğrulama ve Validasyon 
Bölüm  PAPERS 
Yazarlar  
Proje Numarası   
Erken Görünüm Tarihi  8 Haziran 2023 
Yayımlanma Tarihi  8 Haziran 2023 
Gönderilme Tarihi  26 Aralık 2022 
Kabul Tarihi  25 Ocak 2023 
Yayımlandığı Sayı  Yıl 2023 Cilt: Vol:8 Sayı: Issue:1 
The Creative Commons Attribution 4.0 International License is applied to all research papers published by JCS and
a Digital Object Identifier (DOI) is assigned for each published paper.