A Heuristic for the Maximum Independent Set Problem Based on Optimization of a Quadratic Over a Sphere
- Additional Document Info
- View All
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.