Efficient Algorithms for Determining the Maximum Independent Sets in Graphs

Authors : Ali KARCİ

Pages : 144-149

View : 8 | Download : 4

Publication Date : 2020-12-01

Article Type : Research Paper

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.
Keywords : Spanning Tree, Fundamental Cut Sets, Efficient Algorithms, Effects of Nodes