This paper presents algorithmic and implementation enhancements of Reactive Local Search algorithm for the Maximum Clique problem [3]. In addition, we build an empirical complexity model for the CPU time required for a single iteration, and we show that with a careful implementation of the data structures one can achieve a speedup of at least an order of magnitude difference for large size graphs.

Reactive local search for maximum clique: A new implementation / Mascia, Franco; Battiti, Roberto. - ELETTRONICO. - (2007), pp. 1-8.

Reactive local search for maximum clique: A new implementation

Mascia, Franco;Battiti, Roberto
2007-01-01

Abstract

This paper presents algorithmic and implementation enhancements of Reactive Local Search algorithm for the Maximum Clique problem [3]. In addition, we build an empirical complexity model for the CPU time required for a single iteration, and we show that with a careful implementation of the data structures one can achieve a speedup of at least an order of magnitude difference for large size graphs.
2007
Trento
University of Trento. Department of information and communication technology
Reactive local search for maximum clique: A new implementation / Mascia, Franco; Battiti, Roberto. - ELETTRONICO. - (2007), pp. 1-8.
Mascia, Franco; Battiti, Roberto
File in questo prodotto:
File Dimensione Formato  
newclique.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 365.12 kB
Formato Adobe PDF
365.12 kB Adobe PDF Visualizza/Apri

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/11572/357852
 Attenzione

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

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