Dokument: Varianten der Metrischen Dimension spezieller Graphklassen
| Titel: | Varianten der Metrischen Dimension spezieller Graphklassen | |||||||
| Weiterer Titel: | Variants of the Metric Dimension of special graph classes | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=66533 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20240819-112359-4 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Deutsch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Schmitz, Yannick [Autor] | |||||||
| Dateien: |
| |||||||
| Beitragende: | Prof. Dr. Wanke, Egon [Gutachter] Prof. Dr. Rothe, Jörg [Gutachter] | |||||||
| Dewey Dezimal-Klassifikation: | 000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik | |||||||
| Beschreibungen: | Zwei Knoten u, v eines ungerichteten Graphen G werden durch einen Knoten w getrennt, wenn sich die Distanz zwischen u und w von der Distanz zwischen v und w unterscheidet. Eine Teilmenge U der Knotenmenge von G ist eine trennende Menge für G, wenn jedes Knotenpaar durch mindestens einen Knoten aus U getrennt wird. Die Metrische Dimension von G entspricht der Größe einer kleinsten trennenden Menge für G. Das Entscheidungsproblem Metrische Dimension ist die Frage, ob G eine trennende Menge der Größe ≤ k besitzt, für einen gegebenen ungerichteten Graphen G und eine gegebene Zahl k.
Dieses Problem wurde bereits in den 1970ern eingeführt und für zahlreiche Graphklassen untersucht. Zu den bekannteren Ergebnissen zählen zum Beispiel die NP-Vollständigkeit für allgemeine Graphen, planare Graphen, Intervallgraphen, Splitgraphen und Gabriel-Unit-Disc Graphen sowie effiziente Algorithmen für außenplanare Graphen, Co-Graphen, Wheels, Kaktusblockgraphen und Bäume. Seit der Einführung der Metrischen Dimension wurden zahlreiche Varianten des Problems formuliert und untersucht, beispielsweise die Lokale Metrische Dimension, die Adjazenzdimension, die k-Metrische Dimension, die Edge Metric Dimension und die Mixed Metric Dimension, die Starke Metrische Dimension und in der gerichteten Version die gerichtete Metrische Dimension und die gerichtete Starke Metrische Dimension. Auch in der vorliegenden Arbeit werden einige Varianten der Metrischen Dimension auf speziellen Graphklassen betrachtet. Die Arbeit ist wie folgt aufgebaut: Nach einer Einleitung und der Definition grundlegender Begriffe in Kapitel 1 und Kapitel 2 werden in Kapitel 3 die oben genannten Varianten der Metrischen Dimension vorgestellt. Hierzu wird die Problemstellung der jeweiligen Variante definiert sowie ein Überblick über einige dazugehörige Ergebnisse gegeben. In Kapitel 4 wird zu einer der Varianten, der k-Metrischen Dimension, ein NP-Vollständigkeitsbeweis erbracht. Anschließend wird in Kapitel 5 die gerichtete Variante der Metrischen Dimension betrachtet. Zuerst wird ein NP-Vollständigkeitsbeweis für diese Variante für DAGs erbracht, danach werden ungerichtete und gerichtete Co-Graphen definiert. Für letztere wird ein Algorithmus vorgestellt, der die gerichtete Metrische Dimension in linearer Zeit berechnet. In Kapitel 6 folgen Ergebnisse zur Starken Metrischen Dimension. Zu Beginn des Kapitels wird ein Linearzeitalgorithmus für ungerichtete Co-Graphen gezeigt. Danach werden Graphen definiert, die durch die Verknüpfung mehrerer ungerichteter Graphen entstehen. Für diese Graphen wird der strong resolving Graph betrachtet, auf dessen Grundlage die Starke Metrische Dimension berechnet werden kann. Ein entsprechender Algorithmus, der die Starke Metrische Dimension eines Graphen berechnet, indem er den Graphen in seine zweifachen Zusammenhangskomponenten zerlegt, wird am Beispiel dreier Graphklassen erläutert. Außerdem wird der strong resolving Graph distanzerhaltender Graphen bestimmt. Abschließend wird in Kapitel 7 die gerichtete Starke Metrische Dimension betrachtet. Auch für diese Variante wird ein Linearzeitalgorithmus für gerichtete Co-Graphen vorgestellt, welcher auf den Ergebnissen des vorherigen Kapitels aufbaut. Am Ende der Arbeit finden sich ein Ausblick sowie die Veröffentlichungen und die Manuskripte, auf denen diese Arbeit basiert.Two vertices u, v of an undirected graph G are resolved by a vertex w if the distance between u and w differs from the distance between v and w. A subset U of vertices of G is a resolving set for G if every pair of vertices is resolved by at least one vertex of U. The metric dimension of G is the size of a smallest resolving set for G. The decision problem Metric Dimension is the question whether there exists a resolving set of size ≤ k for G, for a given undirected graph G and a given number k. This problem was already introduced in the 1970s and was studied for numerous classes of graphs. The more known results include for example the NP-completeness for general graphs, planar graphs, interval graphs, split graphs and Gabriel unit disc graphs, as well as efficient algorithms for outerplanar graphs, co-graphs, wheels, cactus-block graphs and trees. Since the introduction of the metric dimension, several variants were defined and studied, for example the Local Metric Dimension, the Adjacency Dimension, the k-Metric Dimension, the Edge Metric Dimension and the Mixed Metric Dimension, the Strong Metric Dimension and for the directed version the directed Metric Dimension and the directed Strong Metric Dimension. In this thesis several variants of the metric dimension are studied for certain classes of graphs as well. It is structured as follows: After an introduction and the definition of basic terms in chapter 1 and chapter 2, the variants of the metric dimension mentioned above will be introduced in chapter 3. Their definition as well as a summary of some known results will be given. In chapter 4 it is proven that k-metric dimension is NP-complete. In Chapter 5 the directed metric dimension is considered. At first an NP-completeness proof for DAGs is provided, afterwards undirected and directed co-graphs are defined. An algorithm for computing the directed metric dimension of directed co-graphs in linear time is presented at the end of the chapter. Next, the strong metric dimension is studied in chapter 6. The beginning of the chapter contains a linear time algorithm for undirected co-graphs. Then, graphs which result from merging several undirected graphs are definied. The strong resolving graphs of those graphs are studied, based on which the strong metric dimension can be calculated. An algorithm which computes the strong metric dimension of a graph by decomposing it into its biconnected components explained using grids, cycles and co-graphs as examples. Furthermore, the strong resolving graphs of distance hereditary graphs are determined. Finally, the directed strong metric dimension is studied in chapter 7. A linear time algorithm for directed co-graphs is presented for this variant as well, based on the results of the previous chapters. At the end an outlook as well as a list of the publications and manuscript this thesis is based on is given. | |||||||
| Lizenz: |  Dieses Werk ist lizenziert unter einer Creative Commons Namensnennung 4.0 International Lizenz | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Algorithmen und ihre Anwendungen | |||||||
| Dokument erstellt am: | 19.08.2024 | |||||||
| Dateien geändert am: | 19.08.2024 | |||||||
| Promotionsantrag am: | 24.04.2024 | |||||||
| Datum der Promotion: | 18.07.2024 |
