ETD system

Electronic theses and dissertations repository

 

Tesi etd-09242019-164116


Thesis type
Tesi di laurea magistrale
Author
BRUNELLI, FILIPPO
URN
etd-09242019-164116
Title
Extending graph properties for listing maximal subgraphs in temporal networks
Struttura
MATEMATICA
Corso di studi
MATEMATICA
Supervisors
relatore Prof. Grossi, Roberto
correlatore Dott. Conte, Alessio
Parole chiave
  • reverse search
  • maximal subgraph
  • set system
  • clique
  • temporal network
Data inizio appello
25/10/2019;
Consultabilità
Secretata d'ufficio
Riassunto analitico
The problem of listing subgraphs that satisfy a certain property represents, in many cases, a hard problem. Despite its inner difficulty, driven by the many applications, a lot of algorithms have been studied to optimize the computational and memory cost that is needed to solve this kind of problems. In this work we focus on listing subgraphs that satisfy a certain property and are maximal under inclusion. A successful general formalism to work with these kind of problems is using set systems, since they can model many interesting properties such as cliques, cuts, k-plexes and others.
First we present a general framework, that through the technique of reverse search, consists in a powerful tool for enumerating maximal solutions. Then we present a model of temporal network and apply the more general framework to the specific problem of finding maximal cliques in temporal graphs.
File