SavedAdd your journal

Journals / Bilgisayar Bilimleri / 2020 / Cilt: 5 Sayı: 2

Efficient Algorithms for Determining the Maximum Independent Sets in Graphs

Ali Karci(INONU UNIVERSITY)
Pages
144–149
Publication Date
2020-12-01
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

These effects of nodes are used to determine the elements of maximum independent set.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:It is known that there are many NP-hard and NP-complete problems in graph theory.
📊
Key Findings & Data:The aim of this paper to solve the maximum independent set which is an NP-Hard and NP-Complete problem.
💡
Conclusion & Impact:These effects of nodes are used to determine the elements of maximum independent set.
🔬Design:Araştırma Makalesi
📍Scope:Comprehensive Sample
⚙️Variables:Spanning Tree · Fundamental Cut-Sets · Efficient Algorithms

Abstract

It is known that there are many NP-hard and NP-complete problems in graph theory. The aim of this paper to solve the maximum independent set which is an NP-Hard and NP-Complete problem. In order to solve maximum independent set for given graph, a special spanning tree which is defined in this paper for the first time, is solved to obtain the fundamental cut-sets. The fundamental cut-sets are used to determine the effects of nodes. These effects of nodes are used to determine the elements of maximum independent set.

Özet

It is known that there are many NP-hard and NP-complete problems in graph theory. The aim of this paper to solve the maximum independent set which is an NP-Hard and NP-Complete problem. In order to solve maximum independent set for given graph, a special spanning tree which is defined in this paper for the first time, is solved to obtain the fundamental cut-sets. The fundamental cut-sets are used to determine the effects of nodes. These effects of nodes are used to determine the elements of maximum independent set.

🔖

Cite This Article

Karci, A. (2020). Efficient Algorithms for Determining the Maximum Independent Sets in Graphs. Bilgisayar Bilimleri, Cilt: 5 Sayı: 2, 144–149. https://ajindex.com/articles/1464345

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (12)

  1. Brandstadt, A., Mosca, R., “Maximum weight independent set for Lclaw-free graphs in polynomial time”, Discrete Applied Mathematics, Vol:237, pp:57-64, 2018.
  2. Jarden, A., Levit, V.E., Mandrescu, E.,”Critical and maximum independent sets of a graph”, Discrete Applied Mathematics, Vol: 247, pp:127-134, 2018.
  3. Karci, A., Karci, Ş.,”Determination of Effective Nodes in Graphs”, International Conference on Science, Engineering & Technology, Mecca, Saudi Arabia, pp:25-28, 2020.
  4. Karci, A., “Finding Innovative and Efficient Solutions to NP-Hard and NP-Complete Problems in Graph Theory”, Anatolian Science – Journal of Computer Science, 2020.
  5. 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.
  6. 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.
  7. Lin. M.-S., “Simple linear-time algorithms for counting independent sets in distance-hereditary graphs”, Discrete Applied Mathematics, Vol: 239, pp:144-153, 2018b.
  8. 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.
  9. Oh, S., “Maximal independent sets on a grid graph”, Discrete Mathematics, Vol:340, pp:2762-2768, 2017. Peramau, G., Perkins, W.,”Counting independent sets in cubic graphs of given girth”, Journal of Combinatorial Theory, Series B, Vol:133, pp:2018.
  10. 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.
  11. 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.
  12. 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.