Logo des Repositoriums
 

Neue Graphen-Algorithmen mittels polyedrischer Methoden

dc.contributor.authorTarnawski, Jakub
dc.contributor.editorHölldobler, Steffen
dc.date.accessioned2022-01-24T12:37:18Z
dc.date.available2022-01-24T12:37:18Z
dc.date.issued2020
dc.description.abstractIn dieser Arbeit werden neue Algorithmen für zwei grundlegende Graphenprobleme vorgestellt. Mit Hilfe von linearen Programmen – darunter auch Programme exponentieller Größe – werden Struktureigenschaften ermittelt die vomAlgorithmus verwendet werden. Etwas überraschend können ähnliche polyedrische Methoden in beiden Graphenproblemen angewendet werden. Der erste Teil der Dissertation widmet sich dem asymmetrischen Handlungsreisendenproblem (Asymmetric Traveling Salesman Problem – ATSP), einem Benchmark-Problem der kombinatorischen Optimierung. Bei diesem Problem geht es darum, die kürzeste Tour für einen erichteten und kantengewichteten Graphen zu finden, die alle Knoten besucht. Seit langem galt es als offen, ob es einen Approximationsalgorithmus für dieses Problem mit einer konstanten Güte gibt. Ein Ergebnis dieser Arbeit ist ein solcher Algorithmus. Der zweite Teil der Dissertation widmet sich dem perfekten Matching-Problem. Zudem wurde in den Achtzigerjahren gezeigt, dass es effiziente parallele Algorithmen für das Matching-Problem gibt, sofern die Verwendung von Zufälligkeit zulässig ist. Allerdings ist es noch offen ob das Matching-Problem in der Komplexitätsklasse NC liegt, also ob Zufälligkeit notwending ist. Diese Arbeit zeigt, dass das Matching-Problem in quasi-NC liegt.de
dc.identifier.isbn978-3-88579-775-3
dc.identifier.urihttps://dl.gi.de/handle/20.500.12116/38013
dc.language.isode
dc.publisherGesellschaft für Informatik e.V.
dc.relation.ispartofAusgezeichnete Informatikdissertationen 2019
dc.relation.ispartofseriesLecture Notes in Informatics (LNI) - Proceedings, Volume D-20
dc.titleNeue Graphen-Algorithmen mittels polyedrischer Methodende
dc.typeText/Conference Paper
gi.citation.endPage218
gi.citation.publisherPlaceBonn
gi.citation.startPage209
gi.conference.date17.-20. Mai 2020
gi.conference.locationSchoss Dagstuhl, Deutschland

Dateien

Originalbündel
1 - 1 von 1
Vorschaubild nicht verfügbar
Name:
Tarnawski_Jakub.pdf
Größe:
355.42 KB
Format:
Adobe Portable Document Format