Enrico Carraro
Effective Heuristics for Assessing the Similarity of a Set of Graphs.
Rel. Giovanni Squillero, Stefano Quer. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering), 2022
|
PDF (Tesi_di_laurea)
- Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives. Download (4MB) | Preview |
Abstract: |
The maximum common subgraph problem has been proven to have NP-hard complexity. Despite this theoretical limit, state-of-the-art algorithms made it viable to solve the problem exactly for some applications. This thesis discusses improvements to the state-of-the-art (a branch and bound algorithm with a smart partitioning strategy) in two areas: the generalization of the algorithm to handle sets of graphs and a best-first search space exploration strategy. The original algorithm is not well suited to serve applications where time is constrained, and approximate solutions can be accepted, as it is designed to explore the solution space exhaustively. The proposed heuristics aim to achieve better approximate solutions in time-bounded problem instances. Experiments demonstrated that our heuristics are scalable to multiple threads with low overhead. Finally, they can handle heterogeneous sets of graphs in sensible ways (i.e., discarding graphs that are not similar to most of the set). |
---|---|
Relators: | Giovanni Squillero, Stefano Quer |
Academic year: | 2021/22 |
Publication type: | Electronic |
Number of Pages: | 100 |
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/24966 |
Modify record (reserved for operators) |