Benutzer: Gast  Login
Originaltitel:
Complexity Analysis of Tries and Spanning Tree Problems 
Übersetzter Titel:
Analyse von Tries und Spannbäumen 
Jahr:
2010 
Dokumenttyp:
Dissertation 
Institution:
Fakultät für Informatik 
Betreuer:
Mayr, Ernst W. (Prof. Dr.) 
Gutachter:
Mayr, Ernst W. (Prof. Dr.); Kemper, Alfons (Prof., Ph.D.) 
Sprache:
en 
Fachgebiet:
DAT Datenverarbeitung, Informatik 
Stichworte:
Tries, Retrieval Trees, Smoothed Analysis, Mealy-type perturbation functions, edit perturbations, star-like perturbation functions, Additive Tree Spanners, NP hardness, Graph approximating spanning Trees, Centrality Approximating spanning Trees, 
Übersetzte Stichworte:
Tries, Retrieval Trees, Smoothed Analysis, Mealy-type perturbation functions, Edit-Pertrubationen, stern-ähnliche Stringperturbationsfunktionen, Additive Baumspanner , NP Vollständigkeit, Zentralitäten Approximierende Spannbäume, 
Kurzfassung:
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...    »
 
Übersetzte Kurzfassung:
In dieser Arbeit werden zwei kombinatorische Probleme analysiert, die insbesondere durch Fragen aus dem Bereich der Bioinformatik motiviert sind. Im ersten Teil der Arbeit wird untersucht, inwieweit ein gegebenes Netzwerk durch einen seiner Spannbäume abstrahiert werden kann. Netzwerke treten im Bereich der Bioinformatik immer dann auf, wenn relationale Daten modelliert werden müssen. Ein Beispiel sind metabolische Netzwerke. Das Finden von guten Netzwerkabstraktionen stellt einen wichtigen Schr...    »
 
Mündliche Prüfung:
15.01.2010 
Seiten:
129 
Letzte Änderung:
19.02.2010