Complexity Analysis of Tries and Spanning Tree Problems
Bernd Stefan Eckhardt · mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) · 2010
In this thesis, we consider two combinatorial problems which are fundamental for many computational tasks, for example in contemporary bioinformatics: in the first part, we investigate how well a given network can be abstracted by its spanning trees. Networks are an important tool for modeling relational data such as metabolic networks and finding good network abstractions is a key ingredient for algorithmic analysis of such networks; in the second part, we perform a smoothed analysis of trie height in order to give a sound mathematical explanation for the good practical performance of tries in string matching tasks. String matching operations on DNA or protein sequences are among the most important kind of operations in bioinformatics applications. The importance of those operations is based on the assumption that the function of a gene or protein and its sequence encoding are strongly related.