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

Verification of Karci Algorithm’s Efficiency for Maximum Independent Set Problem in Graph Theory

Yıl 2022, Cilt: Vol: 7 Sayı: Issue: 1, 20 - 28, 06.06.2022
https://doi.org/10.53070/bbd.1090368

Öz

The maximum independent set problem is an NP-complete problem in graph theory. The Karci Algorithm is based on fundamental cut-sets of given graph, and node with minimum independence values are selected for maximum independent set. In this study, the analytical verification of this algorithm for some special graphs was analysed, and the obtained results were explained. The verification of Karci’s Algorithm for maximum independent set was handled in partial.

Kaynakça

  • Karci, A.,”New Algorithms for Minimum Dominating Set in Any Graphs”, Anatolian Science, Journal of Computer Science, Vol:5, Issue:2, pp:62-70, 2020a.
  • Karci, A.,” Finding Innovative and Efficient Solutions to NP-Hard and NP-Complete Problems in Graph Theory”, Anatolian Science, Journal of Computer Science, Vol:5, Issue:2, pp:137-143, 2020b.
  • Karci, A.,” Efficient Algorithms for Determining the Maximum Independent Sets in Graphs”, Anatolian Science, Journal of Computer Science, Vol:5, Issue:2, pp:144-149, 2020c.
  • Karci, A., Karci, Ş.,”Determination of Effective Nodes in Graphs”, International Conference on Science, Engineering & Technology, Mecca, Saudi Arabia, pp:25-28, 2020.
  • Karci, Ş., Ari, A., Karci, A.,” Pençesiz çizgelerde maksimum-yakın bağımsız küme ve üst sınırları için yeni algoritma”, Journal of the Faculty of Engineering and Architecture of Gazi University (accepted).
  • Baraji, S., Swaminathan, V., Kannan, K.,”A simple algorithm to optimize maximum independent set”, Advanced Modeling and Optimization, vol:12, Issue:1, pp:107-118, 2010.
  • Brandstadt, A., Mosca, R., “Maximum weight independent set for Lclaw-free graphs in polynomial time”, Discrete Applied Mathematics, Vol:237, pp:57-64, 2018.
  • Lin, M.-S.,”Counting independent sets and maximal independent sets in some subclasses of bipartite graphs”, Discrete Applied Mathematics, Vol:251, pp:236-244, 2018a.
  • Laflamme, C., Aranda, A., Soukup, D.T., Woodrow, R.,”Balanced independent sets in graphs omitting large cliques”, Journal of Combinatorial Theory, Series B, Vol:137, pp:1-9, 2019.
  • Oh, S., “Maximal independent sets on a grid graph”, Discrete Mathematics, Vol:340, pp:2762-2768, 2017.
  • Wan, P., Tu, J., Zhang, S., Li, B., “Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth”, Applied Mathematics and Computation, Vol:332, pp:42-47, 2018.
  • Lin, M.-S., Chen, C.-M.,”Linear-time algorithms for counting independent sets in bipartite permutation graphs”, Information Processing Letters, Vol:122, pp:1-7, 2017.
  • Lin. M.-S., “Simple linear-time algorithms for counting independent sets in distance-hereditary graphs”, Discrete Applied Mathematics, Vol: 239, pp:144-153, 2018b.
  • Sah, A., Sawhhney, M., Stoner, D., Zhao, Y.,”The number of independent sets in an irregular graph”, Journal of Combinatorial Theory, Series B, Vol:138, pp:172-195, 2019.
  • Jarden, A., Levit, V.E., Mandrescu, E.,”Critical and maximum independent sets of a graph”, Discrete Applied Mathematics, Vol: 247, pp:127-134, 2018.
  • Peramau, G., Perkins, W.,”Counting independent sets in cubic graphs of given girth”, Journal of Combinatorial Theory, Series B, Vol:133, pp:2018.
  • Wan, P., Chen, X., Tu, J., Dehmer, M., Zhang, S., Emmert-Streib, F.,”On graph entropy measures based on the number of independent sets and matchings”, Information Sciences, Vol:516, pp:491-504, 2020.

Verification of Karci Algorithm’s Efficiency for Maximum Independent Set Problem in Graph Theory

Yıl 2022, Cilt: Vol: 7 Sayı: Issue: 1, 20 - 28, 06.06.2022
https://doi.org/10.53070/bbd.1090368

Öz

The maximum independent set problem is an NP-complete problem in graph theory. The Karci Algorithm is based on fundamental cut-sets of given graph, and node with minimum independence values are selected for maximum independent set. In this study, the analytical verification of this algorithm for some special graphs was analysed, and the obtained results were explained. The verification of Karci’s Algorithm for maximum independent set was handled in partial.

Kaynakça

  • Karci, A.,”New Algorithms for Minimum Dominating Set in Any Graphs”, Anatolian Science, Journal of Computer Science, Vol:5, Issue:2, pp:62-70, 2020a.
  • Karci, A.,” Finding Innovative and Efficient Solutions to NP-Hard and NP-Complete Problems in Graph Theory”, Anatolian Science, Journal of Computer Science, Vol:5, Issue:2, pp:137-143, 2020b.
  • Karci, A.,” Efficient Algorithms for Determining the Maximum Independent Sets in Graphs”, Anatolian Science, Journal of Computer Science, Vol:5, Issue:2, pp:144-149, 2020c.
  • Karci, A., Karci, Ş.,”Determination of Effective Nodes in Graphs”, International Conference on Science, Engineering & Technology, Mecca, Saudi Arabia, pp:25-28, 2020.
  • Karci, Ş., Ari, A., Karci, A.,” Pençesiz çizgelerde maksimum-yakın bağımsız küme ve üst sınırları için yeni algoritma”, Journal of the Faculty of Engineering and Architecture of Gazi University (accepted).
  • Baraji, S., Swaminathan, V., Kannan, K.,”A simple algorithm to optimize maximum independent set”, Advanced Modeling and Optimization, vol:12, Issue:1, pp:107-118, 2010.
  • Brandstadt, A., Mosca, R., “Maximum weight independent set for Lclaw-free graphs in polynomial time”, Discrete Applied Mathematics, Vol:237, pp:57-64, 2018.
  • Lin, M.-S.,”Counting independent sets and maximal independent sets in some subclasses of bipartite graphs”, Discrete Applied Mathematics, Vol:251, pp:236-244, 2018a.
  • Laflamme, C., Aranda, A., Soukup, D.T., Woodrow, R.,”Balanced independent sets in graphs omitting large cliques”, Journal of Combinatorial Theory, Series B, Vol:137, pp:1-9, 2019.
  • Oh, S., “Maximal independent sets on a grid graph”, Discrete Mathematics, Vol:340, pp:2762-2768, 2017.
  • Wan, P., Tu, J., Zhang, S., Li, B., “Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth”, Applied Mathematics and Computation, Vol:332, pp:42-47, 2018.
  • Lin, M.-S., Chen, C.-M.,”Linear-time algorithms for counting independent sets in bipartite permutation graphs”, Information Processing Letters, Vol:122, pp:1-7, 2017.
  • Lin. M.-S., “Simple linear-time algorithms for counting independent sets in distance-hereditary graphs”, Discrete Applied Mathematics, Vol: 239, pp:144-153, 2018b.
  • Sah, A., Sawhhney, M., Stoner, D., Zhao, Y.,”The number of independent sets in an irregular graph”, Journal of Combinatorial Theory, Series B, Vol:138, pp:172-195, 2019.
  • Jarden, A., Levit, V.E., Mandrescu, E.,”Critical and maximum independent sets of a graph”, Discrete Applied Mathematics, Vol: 247, pp:127-134, 2018.
  • Peramau, G., Perkins, W.,”Counting independent sets in cubic graphs of given girth”, Journal of Combinatorial Theory, Series B, Vol:133, pp:2018.
  • Wan, P., Chen, X., Tu, J., Dehmer, M., Zhang, S., Emmert-Streib, F.,”On graph entropy measures based on the number of independent sets and matchings”, Information Sciences, Vol:516, pp:491-504, 2020.
Toplam 17 adet kaynakça vardır.

Ayrıntılar

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

Ali Karci 0000-0002-8489-8617

Erken Görünüm Tarihi 5 Haziran 2022
Yayımlanma Tarihi 6 Haziran 2022
Gönderilme Tarihi 19 Mart 2022
Kabul Tarihi 27 Nisan 2022
Yayımlandığı Sayı Yıl 2022 Cilt: Vol: 7 Sayı: Issue: 1

Kaynak Göster

APA Karci, A. (2022). Verification of Karci Algorithm’s Efficiency for Maximum Independent Set Problem in Graph Theory. Computer Science, Vol: 7(Issue: 1), 20-28. https://doi.org/10.53070/bbd.1090368

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.