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. © 1994 Kluwer Academic Publishers.

An exact algorithm for the maximum stable set problem / Mannino, Carlo; Sassano, Antonio. - In: COMPUTATIONAL OPTIMIZATION AND APPLICATIONS. - ISSN 0926-6003. - 3:3(1994), pp. 243-258. [10.1007/bf01299447]

An exact algorithm for the maximum stable set problem

MANNINO, Carlo;SASSANO, Antonio
1994

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. © 1994 Kluwer Academic Publishers.
branch-and-bound; maximum clique; maximum stable set
01 Pubblicazione su rivista::01a Articolo in rivista
An exact algorithm for the maximum stable set problem / Mannino, Carlo; Sassano, Antonio. - In: COMPUTATIONAL OPTIMIZATION AND APPLICATIONS. - ISSN 0926-6003. - 3:3(1994), pp. 243-258. [10.1007/bf01299447]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/244494
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 30
  • ???jsp.display-item.citation.isi??? ND
social impact