In den letzten Jahren wurden komplexere Charakterisierungen von dünnbesetzten Graphen, die nirgendwo-dichte Graphklassen und Graphklassen mit beschränkter Expansionumfassen. Beide fallen in die Kategorie der strukturellen Sparsität und ermöglichen in der Theorie eine Vielzahl effizienter Algorithmen.Während es viele Charakterisierungen für diese Graphklassen gibt, kann eine in Form von schwachen Färbungszahlen angegeben werden. Für jeden Radius r ∈ N werden diese durch lineare Ordnungen von Knoten eines Graphen definiert. Jede Ordnung von Knotenin einem Graphen hat eine schwache r-Färbungszahl, und die schwache r-Färbungszahl eines Graphen ist die minimale schwache r-Färbungszahl der Ordnungen seiner Knoten.Die schwache r-Färbungszahl eines Graphen misst Erreichbarkeitseigenschaften an der Entfernung r, hat aber auch direkte algorithmische Anwendungen.Obwohl es viele Forschungsartikel gibt, die sich auf obere und untere Schranken von schwachen Färbungszahlen in spezifischen Graphklassen konzentrieren, gibt es bis jetzt wenig Forschung in Bezug auf Komplexitätsergebnisse für die Berechnung schwacher r-Färbungszahlen und den Entwurf von Algorithmen zur Berechnung von Ordnungen mit kleinen schwachen Färbungszahlen. Es hat sich gezeigt, dass die Berechnung schwacher r-Färbungszahlen für r ≥ 3 NP-vollständig ist, und daher benötigen wir effiziente Heuristiken, um gute obere Schranken für schwache r-Färbungszahlen zu berechnen.In dieser Arbeit entwerfen wir mehrere Heuristiken zur Berechnung oberer Schranken von schwachen Färbungszahlen, die das Turbocharging-Framework verwenden. In der allgemeinsten Fassung kann das Framework als „Erweitern eines heuristischen Algorithmus mit einem exakten Algorithmus“ beschrieben werden, oder mit anderen Worten, „Turbocharging der Heuristik“. Mittels einiger bekannter Heuristiken entwickeln wir mehrere exakte Algorithmen, die diese Heuristiken lokal ergänzen und zusätzlich beweisen wir obere und untere Komplexitätsgrenzen dieser Algorithmen. Wir implementieren die daraus resultierenden Ansätze und führen eine umfassende experimentelle Auswertung für reale Graphinstanzen durch.Dabei diskutieren wir Vor- und Nachteile des Turbocharging-Ansatzes, die während unserer Forschung auftraten und für zukünftige Forschungen relevant sein könnten.
de
In recent years, more involved characterizations of sparse graphs were introduced, involving nowhere dense graph classes and graph classes of bounded expansion. Both fall into the category of structural sparsity and exhibit a wide variety of efficient algorithms in theory. One characterization for these graph classes can be given in terms of weak coloring numbers. They are defined in terms of vertex orderings of a graph for a given radius r ∈ N.Each ordering has a weak r-coloring number, and the weak r-coloring number of a graph is the minimum weak r-coloring number over all its vertex orderings. The weak r-coloring number of a graph measures reachability properties at distance r, but also has direct algorithmic applications. Although there are many results focusing on upper and lower bounds for weak coloring numbers in specific graph classes, there is little research with regard to complexity results for computing weak r-coloring numbers and designing heuristics that compute vertex orderings with small weak r-coloring number. Computing weak r-coloring numbers is NP-complete for r ≥ 3, and thus we need efficient algorithms to compute good upper bounds on weak r-coloring numbers. In this thesis, we propose several algorithms that compute orderings of small weak coloring numbers by applying the turbocharging framework. In the most general form, the framework can be described as “augmenting a heuristic algorithm with an exact algorithm”, or in other words, “turbocharging the heuristic”. Given some known heuristics that iteratively compute an ordering of small weak coloring numbers, we propose several exact algorithms that locally augment these heuristics, and additionally, prove upper and lower complexity bounds of these algorithms. We implement the resulting approaches and provide a thorough experimental evaluation for real-world graph instances. In the process, we discuss advantages and drawbacks of the turbocharging approach that came up during our research and might be relevant for future research.
