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.

published proceedings

  • Journal of Combinatorial Optimization

author list (cited authors)

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

citation count

  • 34

complete list of authors

  • Busygin, Stanislav||Butenko, Sergiy||Pardalos, Panos M

publication date

  • September 2002