Dokument: Comparing and Computing Parameters for Directed Graphs

Titel:Comparing and Computing Parameters for Directed Graphs
Weiterer Titel:Vergleich und Berechnung von Parametern für gerichtete Graphen
URL für Lesezeichen:https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=59254
URN (NBN):urn:nbn:de:hbz:061-20220503-134237-7
Kollektion:Dissertationen
Sprache:Englisch
Dokumententyp:Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:Text
Autor: Rehs, Carolin [Autor]
Dateien:
[Dateien anzeigen]Adobe PDF
[Details]1,59 MB in einer Datei
[ZIP-Datei erzeugen]
Dateien vom 04.04.2022 / geändert 04.04.2022
Beitragende:PD Dr. Gurski, Frank [Gutachter]
Prof. Dr. Wanke, Egon [Gutachter]
Dewey Dezimal-Klassifikation:000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibung:The field of undirected graph parameters is a very huge one and has been well-researched since the 1980s. A graph parameter, also called width measure, is a function that associates a positive integer with every graph. Probably the most considered undirected graph parameters in literature are path-width and tree-width as well as clique-width . All of these parameters allow strong algorithmic results considering fixed-parameter-tractability. Especially for tree-width and clique-width there is an often cited Theorem by Courcelle, which states that all graph problems describable in monadic second-order logic on quantification over vertices and vertex sets (and additionally on quantification over edges and edge sets) are computable in polynomial time for bounded clique-width (tree-width).
This leads to the question, if there exist directed width measures that are as strong as the undirected ones. There have been numerous attempts to define directed width measures which admit as many algorithmical results as tree-width and path-width and there has been some well-known research to compare these parameters.
Having studied this matter for some time, one comes to the conclusion that none of the known directed width parameters allows as strong results as the undirected ones. However, this does not mean that directed width parameters are not worth working on. Especially when not considered for all digraphs in general, but on special digraph classes, interesting results on these parameters remain possible.
In this work, several width measures on digraphs are considered. We investigate especially directed path-width and directed tree-width, but particularly for tree-width there have been many different attempts to define a directed version. As the idea of undirected tree-width comes from Robertson and Seymour, it seems to be reasonable to consider mainly the paper by Johnson, Robertson, Seymour and Thomas in which they define not only a directed version of tree-width, but also directed path-width. But even they themselves later published an addendum, in which they suggested to slightly change the definition.
We also consider the directed tree-width versions by Reed, by Kreutzer and Ordyniak in “Quantitative Graph Theory”, by Kreutzer and Kwon in “Classes of Directed Graphs” and the idea of Courcelle and Olariu to use the underlying undirected graph. As an interesting fact we can see, that all these different definitions of directed tree-width but the last mentioned are equivalent, which means they only differ by a constant factor.
Other ideas for directed versions of the well-known tree-width that are studied in this work are DAG-width and Kelly-width.
Directed Clique-width and directed NLC-width and their linear versions are definable very similar to their undirected versions. Nevertheless they are interesting to consider, as they allow the strongest algorithmic results on directed graphs in general.
Further directed graph parameters are directed vertex separation number, directed cut-width, directed neighbourhood-width, directed linear rank-width, DFVS-Number, cycle rank, DAG-depth, and directed modular width.
As there are such an amount of different parameters, it seems very likely to compare them. In this work, we first present linear, then non-linear directed graph parameters. Many linear width measures are comparable in general, whereas this is not possible for the non-linear ones. Therefore, we regard several directed graph classes and compare directed width parameters in this restricted area.
On several graph classes, this leads to the computability of these graph parameters in polynomial or even linear time. We give algorithms for the computation of different graph parameters and relations between them on tree-like digraphs, directed co-graphs, their superclass directed distance-hereditary graphs, sequence digraphs and semicomplete graphs.
Lizenz:In Copyright
Urheberrechtsschutz
Fachbereich / Einrichtung:Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik
Dokument erstellt am:03.05.2022
Dateien geändert am:03.05.2022
Promotionsantrag am:12.09.2021
Datum der Promotion:18.03.2022
english
Benutzer
Status: Gast
Aktionen