ETD

Archivio digitale delle tesi discusse presso l'Università di Pisa

Tesi etd-07042017-173038


Tipo di tesi
Tesi di laurea magistrale
Autore
VERSARI, LUCA
URN
etd-07042017-173038
Titolo
A New Algorithmic Framework for Enumerating Commutable Set Properties
Dipartimento
INFORMATICA
Corso di studi
INFORMATICA
Relatori
relatore Prof. Grossi, Roberto
Parole chiave
  • k-plexes
  • graph algorithms
  • enumeration algorithms
  • combinatorial patterns in graphs
  • cliques
  • set systems
Data inizio appello
21/07/2017
Consultabilità
Completa
Riassunto
This thesis considers a new algorithmic framework for listing maximal sets satisfying a given property (e.g. being a clique, a cut, a cycle, etc.), which fall within the general framework of set systems. A set system $\mathcal{F}$ over a ground set $E$ (e.g. the network nodes) is a collection of subsets of $E$ for which there exists some function that checks if an arbitrary subset of $E$ belongs to $\mathcal{F}$. For all \emph{maximal} subsets in $\mathcal{F}$ under inclusion to be listed, the ambitious goal is to cover a large class of set systems while preserving the efficiency of their enumeration algorithms at the same time. The best-known ones list the maximal subsets in time proportional to their number but may require exponential space. This thesis improves the state of the art in two directions by introducing an algorithmic framework that, under suitable conditions, simultaneously (i) extends the class that can be solved efficiently to \emph{commutable set systems}, and (ii) reduces the additional space usage from exponential in $|E|$ to \emph{stateless}, thus accounting for just $O(q)$ space, where $q \leq |E|$ is the largest size of a maximal set.
File