ETD system

Electronic theses and dissertations repository

 

Tesi etd-04052013-150004


Thesis type
Tesi di laurea magistrale
Author
BORASSI, MICHELE
URN
etd-04052013-150004
Title
Telling Stories: Enumerating Maximal Directed Acyclic Subgraphs with a Specified Set of Sources and Targets
Struttura
MATEMATICA
Corso di studi
MATEMATICA
Commissione
relatore Prof. Crescenzi, Pierluigi
Parole chiave
  • DAG
  • directed acyclic subgraph
  • enumeration
Data inizio appello
24/04/2013;
Consultabilità
parziale
Data di rilascio
24/04/2053
Riassunto analitico
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.<br>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.<br>Queste affermazioni verranno provate sperimentalmente nell’ultimo capitolo, utilizzanzo un database di reti metaboliche abbastanza esteso.<br>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.
File