An Augmentation Algorithm for the Maximum Weighted Stable Set Problem |
| |
Authors: | Carlo Mannino Egidio Stefanutti |
| |
Institution: | (1) Dipartimento di Informatica e Sistemistica, Università di Roma La Sapienza, Via Buonarroti 12, 00185, Roma |
| |
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. |
| |
Keywords: | stable set |
本文献已被 SpringerLink 等数据库收录! |