An augmentation algorithm for the maximum weighted stable set problem

An augmentation algorithm for the maximum weighted stable set problem

0.00 Avg rating0 Votes
Article ID: iaor20003677
Country: Netherlands
Volume: 14
Issue: 3
Start Page Number: 367
End Page Number: 381
Publication Date: Nov 1999
Journal: Computational Optimization and Applications
Authors: ,
Keywords: computational analysis
Abstract:

Edge projection is a specialization of Lovász and Plummer's clique reduction when restricted to edges. A concept of augmenting sequences of edge-projections is defined w.r.t. a stable set S. It is then proved the equivalence between the optimality of S and the existence of an augmenting sequence w.r.t. S. This result is then exploited to develop a new tabu-search heuristic for the Maximum Stable Set Problem (weighted and unweighted). The resulting code proved to be competitive with the best codes presented in the literature.

Reviews

Required fields are marked *. Your email address will not be published.