Research Article
BibTex RIS Cite

Efficient Algorithms for Determining the Maximum Independent Sets in Graphs

Year 2020, Volume: 5 Issue: 2, 144 - 149, 01.12.2020

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.

References

  • 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.

Efficient Algorithms for Determining the Maximum Independent Sets in Graphs

Year 2020, Volume: 5 Issue: 2, 144 - 149, 01.12.2020

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.

References

  • 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.
There are 12 citations in total.

Details

Primary Language English
Subjects Software Testing, Verification and Validation
Journal Section PAPERS
Authors

Ali Karci

Publication Date December 1, 2020
Submission Date May 30, 2020
Acceptance Date June 23, 2020
Published in Issue Year 2020 Volume: 5 Issue: 2

Cite

APA Karci, A. (2020). Efficient Algorithms for Determining the Maximum Independent Sets in Graphs. Computer Science, 5(2), 144-149.

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