A Heuristic for the Maximum Independent Set Problem Based on Optimization of a Quadratic Over a Sphere Conference Paper uri icon


  • For a given graph the maximum independent set problem is to find a maximum subset of vertices no two of which are adjacent. We propose a heuristic for the maximum independent set problem which utilizes classical results for the problem of optimization of a quadratic function over a sphere. The efficiency of the approach is confirmed by results of numerical experiments on DIMACS benchmarks.

author list (cited authors)

  • Busygin, S., Butenko, S., & Pardalos, P. M.

citation count

  • 33

publication date

  • September 2002