A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere Conference Paper

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.

authors

• Butenko, Sergiy

published proceedings

• JOURNAL OF COMBINATORIAL OPTIMIZATION

author list (cited authors)

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

citation count

• 37

complete list of authors

• Busygin, S||Butenko, S||Pardalos, PM

publication date

• September 2002

publisher

• Springer Nature  Publisher

published in

• Journal of Combinatorial Optimization  Journal

keywords

• Combinatorial Optimization
• Continuous Approach
• Maximum Independent Set

Digital Object Identifier (DOI)

• 10.1023/A:1014899909753

start page

• 287

end page

• 297

volume

• 6

issue

• 3

URL

• http://dx.doi.org/10.1023/a:1014899909753