On a Polynomial Fractional Formulation for Independence Number of a Graph Academic Article uri icon


  • In this paper we characterize the local maxima of a continuous global optimization formulation for finding the independence number of a graph. Classical Karush-Kuhn-Tucker conditions and simple combinatorial arguments are found sufficient to deduce several interesting properties of the local and global maxima. These properties can be utilized in developing new approaches to the maximum independent set problem. © Springer 2006.

author list (cited authors)

  • Balasundaram, B., & Butenko, S.

citation count

  • 5

publication date

  • July 2006