About Treedepth and Related Notions

Sanchez Villaamil, Fernando; Rossmanith, Peter (Thesis advisor); Fernau, Henning (Thesis advisor)

Aachen (2017, 2018)
Doktorarbeit

Dissertation, RWTH Aachen University, 2017

Kurzfassung

In dieser Doktorarbeit stellen wir verschiedene Ergebnisse in Bezugauf Baumtiefe vor. Als Erstes liefern wir den schnellsten Linearzeit-fpt-Algorithmus, um die Baumtiefe eines Graphen zuberechnen. Er entscheidet, ob ein Graph Baumtiefe d in 2^O(d^2) n Schritten hat. Dabei beantworten wir eine offene Frage von Nešetřil und Ossona de Mendez, in der nach einem einfachen Linearzeit-fpt-Algorithmus gefragt wurde. Als Nächstes vergleichen wir Baumweite und Baumtiefe. Wir beweisen untere Schranken für die Laufzeit und den Platzverbrauch von dynamicprogramming-Algorithmen (auf der Basis einer sinnvollen Definition voneinem dynamic programming-Algorithmus) für Vertex Cover, 3-Coloringund Dominating Set auf einer Baum-, Pfad- oder Baumtiefenzerlegung. Diese Schranken stimmen mit den besten Laufzeiten von bekannten Algorithmen für diese Probleme überein. Es ist nicht schwierig, sich davon zu überzeugen, dass man Vertex Cover und 3-Coloring, parametrisiert mit einer gegebenen Baumtiefenzerlegung mit Tiefe $d$, mit einem Platzverbrauch von poly(d) log n lösen kann. Wir zeigen, dass das Gleiche für Dominating Set möglich ist. Wir analysieren das random intersection graph-Modell, das versucht, Netzwerke zu modellieren, bei denen Verbindungen gemeinsame Attribute der Knoten darstellen. Wir zeigen, dass dieses Modell, derartkonfiguriert, dass es degenerierte Graphen erzeugt, mit hoher Wahrscheinlichkeit Graphen generiert, die zu einer boundedexpansion-Graphklasse gehören. Weiterhin beweisen wir, dass dieses Modell auf andere Weise konfiguriert, Graphen erzeugt, die asymptotisch fast sicher somewhere dense sind. Wir stellen dann einen Algorithmus für motif/subgraph counting auf bounded expansion-Graphenvor, der eine Charakterisierung von bounded expansion-Graphklassen mittels einer Dekomposition des Graphen in Teilen mit beschränkter Baumtiefe ausnutzt. Zuletzt beschreiben wir eine Heuristik, die zuerst eine Baumtiefenzerlegung und daraus eine Baumzerlegung des Graphen berechnet. Wir zeigen, dass diese mit anderen bekannten Heuristiken für Baumzerlegungen konkurrieren kann.

Identifikationsnummern