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 Schritt für die algorithmische Analyse solcher Netze dar. Im zweiten Teil der Arbeit wird das Paradigma der Smoothed Analysis auf die Höhe von Tries angewandt, um deren gutes Laufzeitverhalten in praktischen Anwendungen besser zu erklären. Tries werden in String Matching Operationen verwendet, die deshalb so wichtig für die Bioinformatik sind, weil ein enger Zusammenhang zwischen der Funktion und der Sequenzdarstellung von Genen und Proteinen angenommen werden kann.    «

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...    »