Title

Simple and fast surrogate constraint heuristics for the maximum independent set problem

Document Type

Article

Publication Title

Journal of Heuristics

Abstract

In a recent paper Glover (J. Heuristics 9:175-227, 2003) discussed a variety of surrogate constraint-based heuristics for solving optimization problems in graphs. The key ideas put forth in the paper were illustrated by giving specializations designed for certain covering and coloring problems. In particular, a family of methods designed for the maximum cardinality independent set problem was presented. In this paper we report on the efficiency and effectiveness of these methods based on considerable computational testing carried out on test problems from the literature as well as some new test problems. © 2007 Springer Science+Business Media, LLC.

First Page

571

Last Page

585

DOI

10.1007/s10732-007-9054-y

Publication Date

12-1-2008

This document is currently not available here.

Share

COinS