<div class="csl-bib-body">
<div class="csl-entry">Dobler, A. (2021). <i>Turbocharging heuristics for weak coloring numbers</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2021.91580</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2021.91580
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/19231
-
dc.description.abstract
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
dc.description.abstract
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.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Graphentheorie
de
dc.subject
Graphenalgorithmen
de
dc.subject
Implementierung
de
dc.subject
Algorithmen
de
dc.subject
Turbocharging
de
dc.subject
Parametrisierte Algorithmik
de
dc.subject
Heuristiken
de
dc.subject
Färbungszahlen
de
dc.subject
Strukturelle Sparsität
de
dc.subject
Diskrete Mathematik
de
dc.subject
Graph Theory
en
dc.subject
Graph Algorithms
en
dc.subject
Implementation
en
dc.subject
Algorithms
en
dc.subject
Turbocharging
en
dc.subject
Fixed-Parameter Tractability
en
dc.subject
Heuristics
en
dc.subject
Generalized Coloring Numbers
en
dc.subject
Structural Sparsity
en
dc.subject
Discrete Mathematics
en
dc.title
Turbocharging heuristics for weak coloring numbers
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2021.91580
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Alexander Dobler
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Sorge, Manuel
-
tuw.publication.orgunit
E192 - Institut für Logic and Computation
-
dc.type.qualificationlevel
Diploma
-
dc.identifier.libraryid
AC16411135
-
dc.description.numberOfPages
106
-
dc.thesistype
Diplomarbeit
de
dc.thesistype
Diploma Thesis
en
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
tuw.assistant.staffStatus
staff
-
tuw.advisor.orcid
0000-0003-0454-3937
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
item.mimetype
application/pdf
-
item.openairecristype
http://purl.org/coar/resource_type/c_bdcc
-
item.languageiso639-1
en
-
item.openaccessfulltext
Open Access
-
item.openairetype
master thesis
-
item.grantfulltext
open
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity