Dokument: Characterizations and Algorithms for Special Digraph Classes
| Titel: | Characterizations and Algorithms for Special Digraph Classes | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=59029 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20220314-083303-0 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Englisch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Komander, Dominique [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | PD Dr. Gurski, Frank [Gutachter] Prof. Dr. Wanke, Egon [Gutachter] | |||||||
| Stichwörter: | Algorithms, directed graph class | |||||||
| Dewey Dezimal-Klassifikation: | 000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik | |||||||
| Beschreibung: | The investigation of directed graph classes is highly motivated by the existence of NP-hard problems on directed graphs, which can be solved faster when restricted to special directed graph classes. But besides designing algorithms for hard problems, there are some open spots in the characterization of directed graph classes that are already solved for undirected graphs.
The objective of this work is to expand the research in the field of directed graph classes and show on several examples how we can use the structures of special directed graphs to solve NP-hard problems, in some cases even in linear time. We deepen the understanding of several directed graph classes and show a new directed version of distance-hereditary graphs, namely twin-distance-hereditary graphs, fit them into the hierarchy and characterize them by a set of forbidden induced subdigraphs. We show some properties of this new directed graph class which are algorithmical useful for solving problems on this class. Furthermore, we study some directed graph parameters, compare them on semicomplete digraphs, and show an efficient computation of some directed width parameters on recursive defined directed graph classes as, e.g., directed co-graphs, and related classes. Moreover, we focus on different NP-hard digraph problems, namely the subset sum problem with (weak) digraph constraints, the directed Steiner path cover problem and several vertex and arc colorings on directed and oriented graphs. We show how to solve these problems on various recursive directed graph classes using dynamic programming by exploiting the underlying tree structure of the recursive digraph classes. Doing so, we achieve more efficient algorithms, in some cases we even show linear time solutions. Thus, with this work we take another small step to expand research in the rather young field of directed graph classes. | |||||||
| Lizenz: |  Urheberrechtsschutz | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Algorithmen und ihre Anwendungen | |||||||
| Dokument erstellt am: | 14.03.2022 | |||||||
| Dateien geändert am: | 14.03.2022 | |||||||
| Promotionsantrag am: | 16.12.2021 | |||||||
| Datum der Promotion: | 01.03.2022 |
