ETD

• cliques
• combinatorial patterns in graphs
• enumeration algorithms
• graph algorithms
• k-plexes
• set systems

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.