Questa è una vecchia versione del documento!
Progetto di ASD, anno accademico 2013/14
Questo progetto viene valutato in trentesimi e sostituisce l'esame scritto del corso o il seminario, e non necessita la presentazione del mini-progetto. Può essere scelto il seguente tema oppure un argomento da concordare con il docente.
Progetto in C/C++ (o altro linguaggio da concordare con il docente) per estrarre clique massimali da un grafo (orientato o meno). Dato un grafo G=(V,E), una clique è un sottoinsieme Q di vertici in V, connessi a due a due, cioè per ogni x e y in V esiste un arco (x,y) in E. Una clique Q è massimale se non esiste altra clique Q' massimale che contiene Q (ricordare che entrambe Q e Q' sono sottoinsiemi di vertici in V).
Il progetto è ispirato al graph mining e richiede di prendere un grafo G e un intero k, e di restituire tutte le clique massimali Q che sono contenute in G e che sono composte da almeno k vertici, cioè vale |Q| >= k. Per risolvere il problema occorrono delle tecniche di enumerazione nei grafi (tutorial da consultare, non va letto tutto: parte1, parte2,parte3).