Research Output
Formulations and Algorithms to Find Maximal and Maximum Independent Sets of Graphs
  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.



binary programming, multi-variable polynomial programming, maximal independent sets, maximum independent set, polynomial time algorithms

Monthly Views:

Available Documents