An exact algorithm for the maximum stable set problem |
| |
Authors: | Carlo Mannino Antonio Sassano |
| |
Affiliation: | (1) Dipartimento di Statistica, Probabilità e Statistica Applicata, Università di Roma La Sapienza, Piazzale Aldo Moro 5, 00185 Roma;(2) Dipartimento di Informatica e Sistemistica, Università di Roma La Sapienza, Via Buonarroti 12, 00185 Roma |
| |
Abstract: | We describe a new branch-and-bound algorithm for the exact solution of the maximum cardinality stable set problem. The bounding phase is based on a variation of the standard greedy algorithm for finding a colouring of a graph. Two different node-fixing heuristics are also described. Computational tests on random and structured graphs and very large graphs corresponding to real-life problems show that the algorithm is competitive with the fastest algorithms known so far.This work has been supported by Agenzia Spaziale Italiana. |
| |
Keywords: | Maximum stable set maximum clique branch-and-bound |
本文献已被 SpringerLink 等数据库收录! |