Publications

In dieser Dissertation beschäftigen wir uns mit mehreren Problemen in gerichteten Graphen. Zuerst betrachten wir das Problem der Berechnung der $2$-fach knotenzusammenhängenden Komponenten in gerichteten Graphen. Wir präsentieren einen neuen Algorithmus zur Lösung dieses Problems in Zeit $O(nm)$ und wir betrachten drei Anwendungen dieses Algorithmus. Sei $G=(V,E)$ ein gerichteter Graph. Ein $2$-gerichteter Block in $G$ ist eine maximale Knotenmenge $C^{2d}\subseteq V$ mit $|C^{2d}|\geq 2$, so dass für jedes Paar von verschiedenen Knoten $x,y\in C^{2d}$ zwei knoten disjunkte Wege von $x$ nach $y$ und zwei knoten disjunke Wege von $y$ nach $x$ in $G$ existieren.Wir präsentieren zwei Algorithmen zur Berechnung der $2$-gerichteten Blöcke von $G$ in Zeit $O(\min\lbrace m,(t_{sap}+t_{sb})n\rbrace n)$, wobei $t_{sap}$ die Anzahl der starken Artikulations\-punkte von $G$ und $t_{sb}$ die Anzahl der starken Brücken von $G$ ist. Wir untersuchen zwei weitere relevante Begriffe: die $2$-starken Blöcke und die $2$-Kanten-Blöcke von $G$. Wir geben zwei Algorithmen zur Berechnung der $2$-starken Blöcke von $G$in Zeit $O( \min \lbrace m,t_{sap} n\rbrace n)$ an und wir zeigen, dass die $2$-Kanten-Blöcke von $G$ in Zeit $O(\min \lbrace m, t_{sb} n \rbrace n)$ bestimmt werden können. Wir untersuchen auch einige Optimierungsprobleme, die mit starken Artikulationspunkten und $2$-Blöcken zusammenhängen. Gegeben sei ein stark zusammenhängender Graph $G=(V,E)$. Wir wollen einen minimalen stark zusammenhängenden spannenden Teilgraphen $G^{*}=(V,E^{*})$ von $G$ finden, so dass die starken Artikulationspunkte von $G$ mit den starken Artikulationspunkten von $G^{*}$ übereinstimmen. Wir zeigen, dass es einen $17/3$-Approximationsalgorithmus für dieses NP-schwere Problem gibt, der lineare Laufzeit hat. Wir betrachten auch das Problem der Berechnung eines minimalen stark zusammenhängenden spannenden Teilgraphen mit denselben $2$-Blöcken in einem stark zusammenhängenden Graphen. Wir präsentieren Approximationsalgorithmen für drei Versionen dieses Problems, die sich in der Art der $2$-Blöcke unterscheiden. Im Gegensatz zu $2$-stark-zusammenhängenden Komponenten kann Entfernung der nicht zu $2$-gerichteten Blöcken gehörenden starken Artikulations\-punkte aus $G$ diese Blöcke ändern. Wir untersuchen das Problem der Berechnung einer minimalen Teilmenge $V^{*}$ der starken Artikulationspunkte, die nicht in diesen Blöcke liegen, so dass das Entfernen von $V^{*}$ denselben Effekt hat. Außerdem untersuchen wir andere Versionen dieses Problems, die sich in der Art der $2$-Blöcke unterscheiden. Ein gerichteter Graph $G=(V,E)$ heißt einfach zusammenhängend, wenn für jedes Paar von Knoten $v,w\in V$ höchstens ein einfacher Weg von $v$ nach $w$ in $G$ existiert. Buchsbaum und Carlisle (1993) gaben einen Algorithmus an, der in Zeit $O(n^{2})$ überprüft, ob $G$ einfach zusammenhängend ist. In dieser Dissertation beschreiben wir eine verbesserte Version dieses Algorithmus, die Laufzeit $O(s\cdot t+m)$ hat, wobei $s,t$ die Anzahl der Quellen beziehungsweise Senken im reduzierten Graphen sind, den man auf folgende Weise erhält: Kontrahieren jeder stark zusammenhängenden Komponente zu einem Knoten und dann Eliminierung von Knoten mit Eingangsgrad oder Ausgangsgrad $1$ durch eine Kontrahierenoperation. Außerdem zeigen wir, dass das Problem der Berechnung einer Kantenteilmenge $C\subseteq E$ (beziehungsweise Knotenteilmenge $F\subseteq V$), deren Löschen einen einfach-zusammenhängenden Graphen übrig lässt, NP-schwer ist.

Im ersten Teil der vorliegenden Arbeit werden Multi-Pivot-Quicksort-Algorithmen betrachtet. Die Idee mehr als ein Pivotelement im Quicksort-Algorithmus zu nutzen, erschien über viele Jahre als unpraktikabel. Dies änderte sich, als im Jahr 2009 ein Dual-Pivot-Algorithmus von V. Yaroslavskiy zum Standard-Sortierverfahren in Java 7 wurde. Die vorliegende Arbeit stellt eine Studie von Multi-Pivot-Quicksort-Algorithmen dar, also Quicksort-Varianten, die mit mehr als einem Pivotelement arbeitet. Sie beschreibt die Konstruktionsprinzipien von 2-Pivot-Algorithmen in Bezug auf die bei der Sortierung notwendigen Schlüsselvergleiche. Ein Ergebnis dieser Untersuchung sind zwei optimale und leicht zu implementierende 2-Pivot-Algorithmen. Die Verallgemeinerung auf >= 3 Pivotelemente benötigt nur kleine Anpassungen. Diese Arbeit betrachtet außerdem die theoretische Analyse von Kostenmaßen, die es ermöglichen, Multi-Pivot-Quicksort-Algorithmen hinsichtlich ihres Speicher- und Cacheverhaltens zu vergleichen. Sie schließt mit einer Laufzeitstudie der besprochenen Algorithmen. Der zweite Teil der Arbeit beschäftigt sich mit dem Einsatz von Hashfunktionen in Algorithmen und Datenstrukturen. Hashfunktionen bilden eine Kernkomponente, z.B. beim Aufbau einer Hashtabelle oder bei Lastbalancierung. Oft wird dabei eine unrealistische Annahme getätigt : Die Hashwerte seien voll zufällig. Die Speicherplatzkomplexität einer solchen Funktion ist für den praktischen Einsatz für unverhältnismäßig hoch. Das Ziel ist, einfache Konstruktionen zu finden, deren Zufallseigenschaften beweisbar gut sind. Diese Arbeit beschreibt eine solche einfache Konstruktion von Hashfunktionen, die in einer Vielzahl von Anwendungen beweisbar gut ist. Zu diesen Anwendungen zählen Cuckoo Hashing mit einem sogenannten Stash, die Konstruktion einer perfekten Hashfunktion, die Simulation einer uniformen Hashfunktion, verschiedene Algorithmen zur Lastbalancierung und verallgemeinertes Cuckoo Hashing in einer leicht abgeschwächten Variante mit verschiedenen Einfügealgorithmen. Der zentrale Beitrag dieser Dissertation ist ein einheitliches Analysekonzept. Dieses ermöglicht es, eine auf Hashfunktionen basierende Datenstruktur oder einen auf Hashfunktionen basierenden Algorithmus nur mit Mitteln der Theorie von Zufallsgraphen zu analysieren, ohne Details der Hashfunktion offenzulegen.

Wir betrachten randomisierte Algorithmen, die bei Eingabe einer Menge S von n Schlüsseln aus einem Universum U, oder einer Menge von n Schlüssel-Wert-Paaren eine Datenstruktur für eine der folgenden Aufgaben bauen. Bei Aufruf der Operation lookup für einen Schlüssel x aus U: * Entscheide, ob x Element von S ist (Mengenzugehörigkeitstester [MZT]). * Falls x aus S ist, gib den Wert zurück welcher x zugeordnet ist. Ansonsten gib einen Wert mit der Interpretation "x ist nicht aus S" zurück (Wörterbuch [WB]) oder gib einen beliebigen Wert zurück (Retrieval-Datenstruktur [RDS]). * Falls x aus S ist, gib eine von x abhängige natürliche Zahl zurück, wobei für alle x aus S diese Zahlen paarweise verschieden sind und ihr Wertebereich in etwa die Größe n hat (perfekte Hashfunktion [PHF]). Die Datenstrukturen die wir behandeln sind Varianten von Cuckoo-Hashing und des Bloomier-Filters, welchen die gleiche einfache Struktur zu Grunde liegt. Sie bestehen aus einer Tabelle mit m Zellen der Breite r Bits sowie einer konstanten Anzahl an Hashfunktionen, welche benutzt werden, um die Elemente aus U auf eine konstante Anzahl an Tabellenzellen abzubilden. Unter der Annahme voll zufälliger Hashfunktionen beschäftigen wir uns damit, wie diese Datenstrukturen in Linearzeit (bezüglich n) konstruiert werden können und welche Ladung n/m bzw. welcher Platzverbrauch m&hahog;r in Abhängigkeit vom Zeitbedarf für lookup erreicht werden kann. Dies führt zu der Frage, ob ein bipartiter Zufallsgraph mit n Knoten (Schlüsseln) links und m Knoten (Zellen) rechts und Kanten bestimmt über die Hashfunktionenein Matching eines bestimmten Typs hat und darüber hinaus, wie solch ein Matching effizient berechnet werden kann. Schwerpunkte der Dissertation sind: * die Optimierung der Lookup-Zeit für WB und MZT (basierend auf Cuckoo-Hashing) bezüglich: (i) einer Beschränkung der durchschnittlichen Anzahl an Zellenzugriffen, (ii) der erwarteten Anzahl an Seitenzugriffen unter der Annahme, dass die Tabelle (Speicher) in Speicherseiten gleicher Größe unterteilt ist. * die Minimierung des Platzbedarfs von RDS und PHF (basierend auf dem Bloomier-Filter), wobei für jeden Schlüssel die Anzahl der Zellenzugriffe nach oben durch eine Konstante beschränkt ist. * eine effiziente Simulation voll zufälliger Hashfunktionen, welche von allen behandelten Datenstrukturen vorausgesetzt werden