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

Stanislav Busygin (), Sergiy Butenko () and Panos M. Pardalos ()
Additional contact information
Stanislav Busygin: Contentsoft AG
Sergiy Butenko: University of Florida
Panos M. Pardalos: Contentsoft AG

Journal of Combinatorial Optimization, 2002, vol. 6, issue 3, No 4, 287-297

Abstract: 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 (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1023/A:1014899909753 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:6:y:2002:i:3:d:10.1023_a:1014899909753

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1014899909753

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().