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
|
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. |
---|---|
Relators: | Stefano Quer |
Academic year: | 2021/22 |
Publication type: | Electronic |
Number of Pages: | 69 |
Subjects: | |
Corso di laurea: | Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering) |
Classe di laurea: | New organization > Master science > LM-32 - COMPUTER SYSTEMS ENGINEERING |
Aziende collaboratrici: | UNSPECIFIED |
URI: | http://webthesis.biblio.polito.it/id/eprint/21140 |
Modify record (reserved for operators) |