A Heuristic for the Maximum Independent Set Problem Based on Optimization of a Quadratic Over a Sphere |
| |
| Authors: | Stanislav Busygin Sergiy Butenko Panos M Pardalos |
| |
| Institution: | (1) Contentsoft AG, Munich, Germany;(2) Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA |
| |
| Abstract: | 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. |
| |
| Keywords: | maximum independent set continuous approach combinatorial optimization |
| 本文献已被 SpringerLink 等数据库收录！ |
