Please use this identifier to cite or link to this item: http://hdl.handle.net/2307/670
Title: Il problema della massima clique : teoria & pratica
Authors: Viale, Massimiliano
metadata.dc.contributor.advisor: Raimondi, Roberto
Issue Date: 3-Feb-2009
Publisher: Università degli studi Roma Tre
Abstract: Il problema di trovare le clique di un grafo appartiene a quel gruppo di problemi combinatoriali considerati un "paradigma" nell'ambito della Teoria della Complessità Computazionale. L'idea principale di questo lavoro è quella di sfruttare la meccanica statistica, la teoria sui vetri di spin e le proprietà delle catene di Markov per creare, comprendere e sviluppare due nuovi algoritmi random per la ricerca della clique: un Metropolis (M) con dinamica alla Glauber ed un algoritmo ispirato al metodo della cavità (C). La possibilità di associare questi algoritmi a modelli disordinati di gas su reticolo, ci permette di utilizzare strumenti tipici della fisica teorica per valutarne caratteristiche e peculiarità. La novità principale rispetto agli altri algoritmi standard che C e M possono esibire è la possibilità di "camminare" su configurazioni che non sono cliques. In questa maniera sembrano avere a disposizione più vie d'uscita quando rimangono intrappolati in uno "stato metastabile" che non sia l'ottimo. Al confronto con altri algoritmi random più famosi, le prestazioni di questi nuovi algoritmi sono decisamente migliori. In particolare, alla luce di costosissime simulazioni numeriche, la dinamica originale di C, che ha oltretutto il vantaggio di essere teoricamente ben comprensibile ed in grado di presentare adeguatamente le problematiche in gioco, sembra decisamente promettente.
URI: http://hdl.handle.net/2307/670
Appears in Collections:X_Dipartimento di Fisica 'Edoardo Amaldi'
T - Tesi di dottorato

Files in This Item:
File Description SizeFormat
CliqueProblemPhD_VialeM.pdf1.03 MBAdobe PDFView/Open
CliqueProblemPhD_VialeM.ps2.08 MBPostscriptView/Open
SFX Query Show full item record Recommend this item

Page view(s)

9
checked on Aug 8, 2020

Download(s)

22
checked on Aug 8, 2020

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.