Öz
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.
Anahtar Kelimeler
Spanning Tree Fundamental Cut-Sets Efficient Algorithms Effects of Nodes
Kaynakça
- Brandstadt, A., Mosca, R., “Maximum weight independent set for Lclaw-free graphs in polynomial time”, Discrete Applied Mathematics, Vol:237, pp:57-64, 2018.
- Jarden, A., Levit, V.E., Mandrescu, E.,”Critical and maximum independent sets of a graph”, Discrete Applied Mathematics, Vol: 247, pp:127-134, 2018.
- Karci, A., Karci, Ş.,”Determination of Effective Nodes in Graphs”, International Conference on Science, Engineering & Technology, Mecca, Saudi Arabia, pp:25-28, 2020.
- Karci, A., “Finding Innovative and Efficient Solutions to NP-Hard and NP-Complete Problems in Graph Theory”, Anatolian Science – Journal of Computer Science, 2020.
- 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.
- 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.
- Lin. M.-S., “Simple linear-time algorithms for counting independent sets in distance-hereditary graphs”, Discrete Applied Mathematics, Vol: 239, pp:144-153, 2018b.
- 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.
- 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.
- 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.
- 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.
- 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.
Öz
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.
Anahtar Kelimeler
Spanning Tree Fundamental Cut-Sets Efficient Algorithms Effects of Nodes
Kaynakça
- Brandstadt, A., Mosca, R., “Maximum weight independent set for Lclaw-free graphs in polynomial time”, Discrete Applied Mathematics, Vol:237, pp:57-64, 2018.
- Jarden, A., Levit, V.E., Mandrescu, E.,”Critical and maximum independent sets of a graph”, Discrete Applied Mathematics, Vol: 247, pp:127-134, 2018.
- Karci, A., Karci, Ş.,”Determination of Effective Nodes in Graphs”, International Conference on Science, Engineering & Technology, Mecca, Saudi Arabia, pp:25-28, 2020.
- Karci, A., “Finding Innovative and Efficient Solutions to NP-Hard and NP-Complete Problems in Graph Theory”, Anatolian Science – Journal of Computer Science, 2020.
- 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.
- 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.
- Lin. M.-S., “Simple linear-time algorithms for counting independent sets in distance-hereditary graphs”, Discrete Applied Mathematics, Vol: 239, pp:144-153, 2018b.
- 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.
- 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.
- 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.
- 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.
- 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.
Ayrıntılar
| Birincil Dil | İngilizce |
|---|---|
| Konular | Yazılım Testi, Doğrulama ve Validasyon |
| Bölüm | PAPERS |
| Yazarlar | |
| Yayımlanma Tarihi | 1 Aralık 2020 |
| Gönderilme Tarihi | 30 Mayıs 2020 |
| Kabul Tarihi | 23 Haziran 2020 |
| Yayımlandığı Sayı | Yıl 2020 Cilt: 5 Sayı: 2 |
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.