polito.it
Politecnico di Torino (logo)

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

Lorenzo Cardone

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

Rel. Stefano Quer. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering), 2021

[img]
Preview
PDF (Tesi_di_laurea) - Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (1MB) | Preview
Abstract:

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.

Relatori: Stefano Quer
Anno accademico: 2021/22
Tipo di pubblicazione: Elettronica
Numero di pagine: 69
Soggetti:
Corso di laurea: Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering)
Classe di laurea: Nuovo ordinamento > Laurea magistrale > LM-32 - INGEGNERIA INFORMATICA
Aziende collaboratrici: NON SPECIFICATO
URI: http://webthesis.biblio.polito.it/id/eprint/21140
Modifica (riservato agli operatori) Modifica (riservato agli operatori)