Politecnico di Torino (logo)

Effective Heuristics for Assessing the Similarity of a Set of Graphs

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

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
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) Modify record (reserved for operators)