Araştırma Makalesi
BibTex RIS Kaynak Göster

A New Approach Based on Centrality Value in Solving the Maximum Independent Set Problem: Malatya Centrality Algorithm

Yıl 2023, , 16 - 23, 08.06.2023
https://doi.org/10.53070/bbd.1224520

Öz

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 NP-Complete 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.

Destekleyen Kurum

-

Proje Numarası

-

Teşekkür

-

Kaynakça

  • Alkhouri, I. R., Atia, G. K., & Velasquez, A. (2022). A differentiable approach to the maximum independent set problem using dataless neural networks. Neural Networks, 155, 168–176. Retrieved from https://doi.org/10.1016/j.neunet.2022.08.008
  • Araujo, F., Farinha, J., Domingues, P., Silaghi, G. C., & Kondo, D. (2011). A maximum independent set approach for collusion detection in voting pools. Journal of Parallel and Distributed Computing, 71(10), 1356–1366. Retrieved from https://doi.org/10.1016/j.jpdc.2011.06.004
  • Ballard-myer, J. C. (2019). Deterministic Greedy Algorithm for Maximum Independent Set Problem in Graph Theory, 1–14.
  • Borgatti, S. P. (2005). Centrality and network flow. Social Networks, 27(1), 55–71. Retrieved from https://doi.org/10.1016/j.socnet.2004.11.008
  • Brandstädt, A., & Mosca, R. (2018). Maximum weight independent set for lclaw-free graphs in polynomial time Discrete Applied Mathematics, 237, 57–64. Retrieved from https://doi.org/10.1016/j.dam.2017.11.029
  • Cormen, T. H., Leiserson, C. E., Rivest, R., & Clifford, S. (2001). Introduction to algorithms (Introducti). London.
  • Das, G. K., De, M., Kolay, S., Nandy, S. C., & Sur-Kolay, S. (2015). Approximation algorithms for maximum independent set of a unit disk graph. Information Processing Letters, 115(3), 439–446. Retrieved from https://doi.org/10.1016/j.ipl.2014.11.002
  • Großmann, E., Lamm, S., Schulz, C., & Strash, D. (2022). Finding Near-Optimal Weight Independent Sets at Scale. Retrieved from http://arxiv.org/abs/2208.13645
  • Joo, C., Lin, X., Ryu, J., & Shroff, N. B. (2016). Distributed Greedy Approximation to Maximum Weighted Independent Set for Scheduling With Fading Channels. IEEE/ACM Transactions on Networking, 24(3), 1476–1488. Retrieved from https://doi.org/10.1109/TNET.2015.2417861
  • Karci, A. (2020). Efficient Algorithms for Determining the Maximum Independent Sets in Graphs. Computer Science, 5(2), 144–149.
  • Karci, A. (2022). Verification of Karci Algorithm’s Efficiency for Maximum Independent Set Problem in Graph Theory. Computer Science, 20–28. Retrieved from https://doi.org/10.53070/bbd.1090368
  • Karcı, A., Yakut, S., & Öztemiz, F. (2022). A New Approach Based on Centrality Value in Solving the Minimum Vertex Cover Problem: Malatya Centrality Algorithm. Computer Science, 55(35), 1–100. Retrieved from https://doi.org/10.53070/bbd.1195501
  • Kumar, G., Duhan, N., & Sharma, A. K. (2011). Page ranking based on number of visits of links of Web page. In 2011 2nd International Conference on Computer and Communication Technology (ICCCT-2011) (pp. 11– 14). IEEE. Retrieved from https://doi.org/10.1109/ICCCT.2011.6075206
  • Lamm, S., Schulz, C., Strash, D., Williger, R., & Zhang, H. (2019). Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs. In 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX) (Vol. January, pp. 144–158). Philadelphia, PA: Society for Industrial and Applied Mathematics. Retrieved from https://doi.org/10.1137/1.9781611975499.12
  • Li, Z., He, G., Xu, D., & Wang, S. (2020). Evaluation of Centralized Reader Anti-Collision Protocols for Mobile RFID System Based on Maximum Independent Set: A Simulation Study. IEEE Access, 8, 123381–123397.23 Retrieved from https://doi.org/10.1109/ACCESS.2020.3006162
  • Thulasiraman, K., & Swamy NS, M. (2011). Graphs: theory and algorithms. Montreal: John Wiley & Sons.
  • Uçkan, T., & Karcı, A. (2020). Extractive multi-document text summarization based on graph independent sets. Egyptian Informatics Journal, 21(3), 145–157. Retrieved from https://doi.org/10.1016/j.eij.2019.12.002
  • Wan, P., Tu, J., Zhang, S., & Li, B. (2018). Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth. Applied Mathematics and Computation, 332, 42–47. Retrieved from https://doi.org/10.1016/j.amc.2018.03.017
  • Xiao, M., & Nagamochi, H. (2017). Exact algorithms for maximum independent set. Information and Computation, 255, 126–146. Retrieved from https://doi.org/10.1016/j.ic.2017.06.001

A New Approach Based on Centrality Value in Solving the Maximum Independent Set Problem: Malatya Centrality Algorithm

Yıl 2023, , 16 - 23, 08.06.2023
https://doi.org/10.53070/bbd.1224520

Öz

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 NP-Complete 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.

Proje Numarası

-

Kaynakça

  • Alkhouri, I. R., Atia, G. K., & Velasquez, A. (2022). A differentiable approach to the maximum independent set problem using dataless neural networks. Neural Networks, 155, 168–176. Retrieved from https://doi.org/10.1016/j.neunet.2022.08.008
  • Araujo, F., Farinha, J., Domingues, P., Silaghi, G. C., & Kondo, D. (2011). A maximum independent set approach for collusion detection in voting pools. Journal of Parallel and Distributed Computing, 71(10), 1356–1366. Retrieved from https://doi.org/10.1016/j.jpdc.2011.06.004
  • Ballard-myer, J. C. (2019). Deterministic Greedy Algorithm for Maximum Independent Set Problem in Graph Theory, 1–14.
  • Borgatti, S. P. (2005). Centrality and network flow. Social Networks, 27(1), 55–71. Retrieved from https://doi.org/10.1016/j.socnet.2004.11.008
  • Brandstädt, A., & Mosca, R. (2018). Maximum weight independent set for lclaw-free graphs in polynomial time Discrete Applied Mathematics, 237, 57–64. Retrieved from https://doi.org/10.1016/j.dam.2017.11.029
  • Cormen, T. H., Leiserson, C. E., Rivest, R., & Clifford, S. (2001). Introduction to algorithms (Introducti). London.
  • Das, G. K., De, M., Kolay, S., Nandy, S. C., & Sur-Kolay, S. (2015). Approximation algorithms for maximum independent set of a unit disk graph. Information Processing Letters, 115(3), 439–446. Retrieved from https://doi.org/10.1016/j.ipl.2014.11.002
  • Großmann, E., Lamm, S., Schulz, C., & Strash, D. (2022). Finding Near-Optimal Weight Independent Sets at Scale. Retrieved from http://arxiv.org/abs/2208.13645
  • Joo, C., Lin, X., Ryu, J., & Shroff, N. B. (2016). Distributed Greedy Approximation to Maximum Weighted Independent Set for Scheduling With Fading Channels. IEEE/ACM Transactions on Networking, 24(3), 1476–1488. Retrieved from https://doi.org/10.1109/TNET.2015.2417861
  • Karci, A. (2020). Efficient Algorithms for Determining the Maximum Independent Sets in Graphs. Computer Science, 5(2), 144–149.
  • Karci, A. (2022). Verification of Karci Algorithm’s Efficiency for Maximum Independent Set Problem in Graph Theory. Computer Science, 20–28. Retrieved from https://doi.org/10.53070/bbd.1090368
  • Karcı, A., Yakut, S., & Öztemiz, F. (2022). A New Approach Based on Centrality Value in Solving the Minimum Vertex Cover Problem: Malatya Centrality Algorithm. Computer Science, 55(35), 1–100. Retrieved from https://doi.org/10.53070/bbd.1195501
  • Kumar, G., Duhan, N., & Sharma, A. K. (2011). Page ranking based on number of visits of links of Web page. In 2011 2nd International Conference on Computer and Communication Technology (ICCCT-2011) (pp. 11– 14). IEEE. Retrieved from https://doi.org/10.1109/ICCCT.2011.6075206
  • Lamm, S., Schulz, C., Strash, D., Williger, R., & Zhang, H. (2019). Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs. In 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX) (Vol. January, pp. 144–158). Philadelphia, PA: Society for Industrial and Applied Mathematics. Retrieved from https://doi.org/10.1137/1.9781611975499.12
  • Li, Z., He, G., Xu, D., & Wang, S. (2020). Evaluation of Centralized Reader Anti-Collision Protocols for Mobile RFID System Based on Maximum Independent Set: A Simulation Study. IEEE Access, 8, 123381–123397.23 Retrieved from https://doi.org/10.1109/ACCESS.2020.3006162
  • Thulasiraman, K., & Swamy NS, M. (2011). Graphs: theory and algorithms. Montreal: John Wiley & Sons.
  • Uçkan, T., & Karcı, A. (2020). Extractive multi-document text summarization based on graph independent sets. Egyptian Informatics Journal, 21(3), 145–157. Retrieved from https://doi.org/10.1016/j.eij.2019.12.002
  • Wan, P., Tu, J., Zhang, S., & Li, B. (2018). Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth. Applied Mathematics and Computation, 332, 42–47. Retrieved from https://doi.org/10.1016/j.amc.2018.03.017
  • Xiao, M., & Nagamochi, H. (2017). Exact algorithms for maximum independent set. Information and Computation, 255, 126–146. Retrieved from https://doi.org/10.1016/j.ic.2017.06.001
Toplam 19 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Konular Yazılım Mühendisliği, Yazılım Testi, Doğrulama ve Validasyon
Bölüm PAPERS
Yazarlar

Selman Yakut 0000-0002-0649-1993

Furkan Öztemiz 0000-0001-5425-3474

Ali Karci 0000-0002-8489-8617

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

Kaynak Göster

APA Yakut, S., Öztemiz, F., & Karci, A. (2023). A New Approach Based on Centrality Value in Solving the Maximum Independent Set Problem: Malatya Centrality Algorithm. Computer Science, Vol:8(Issue:1), 16-23. https://doi.org/10.53070/bbd.1224520

The Creative Commons Attribution 4.0 International License 88x31.png  is applied to all research papers published by JCS and

a Digital Object Identifier (DOI)     Logo_TM.png  is assigned for each published paper.