Formulations and Algorithms to Find Maximal and Maximum Independent Sets of Graphs
Maher Heal, Kia K. Dashtipour, Mandar Gogate · 2022
We propose four algorithms to find maximal and maximum independent sets of graphs. Two of the algorithms are non-polynomial in time, mainly binary programming and non-convex multi-variable polynomial programming algorithms. Two other algorithms run in polynomial time seek to find a maximum independent set. The algorithms depend on our earlier work in [10]. The main advantage and the difference of the new algorithms is that we do not need to enumerate the maximal cliques of the graphs. We applied the algorithms to some graphs from DIMACS and other graphs and their performance was seen to be adequate.