Problema del Massimo Comune Sottografo: Concorrenza ed Estensioni per Multipli Grafi = The Maximum Common Subgraph problem: Concurrency and Multi-Graph Extentions

Il problema del Massimo Comune Sottografo (MCS) è ben noto in letteratura. Esso consiste nel trovare il più ampio grafo che è simultaneamente isomorfo rispetto a due dati grafi. Trovare questo grafo è stato dimostrato essere un problema di complessità NP-hard e, pertanto, ci si è spesso limitati a trovare delle soluzioni non esatte di dimensione non massima. Nonostante la complessità del problema in alcuni campi questo non è sufficiente e, grazie anche al costante aumento della potenza di calcolo dei nostri dispositivi, diversi approcci sempre più efficienti tentano di ottenere una soluzione esatta al problema. Questa tesi si concentra sull’estensione dell’algoritmo McSplit, un algoritmo di partizionamento per i problemi di massimo comune sottografo. I nostri sforzi si sono diretti in due principali direzioni: estendere l’algoritmo originale, in modo tale da permettere di risolvere il problema del massimo comune sottografo tra un numero N di grafi, e migliorare l’implementazione many-core presentata da Gabriele Mosca nella sua tesi, tramite una migliore selezione dei nodi su cui proseguire la ricerca.