• DAG
• directed acyclic subgraph
• enumeration

Questa tesi presenta un algoritmo che enumera con ritardo lineare tutti i sottografi aciclici di un dato digrafo G=(V,E), le cui sorgenti e i cui pozzi sono contenuti rispettivamente in due sottoinsiemi fissati S e T di V.
Da questi sottografi, chiamati pitches, quelli massimali, chiamati storie, possono essere estratti in modo nettamente più efficiente rispetto all’unico algoritmo già esistente. Il miglioramento può diventare ancora più significativo se viene applicata una tecnica di pruning, che evita che siano generati molti pitches da cui non si può ottenere una storia.
Queste affermazioni verranno provate sperimentalmente nell’ultimo capitolo, utilizzanzo un database di reti metaboliche abbastanza esteso.
Tutti i risultati originali presenti in questa tesi saranno presentati dall’autore al 12th International Simposium on Exponential Algorithms (SEA), 5-7 giugno 2013, Roma. Saranno inoltre pubblicati da Lecture Notes in Computer Science.