Dokument: Die Metrische Dimension spezieller Graphklassen
| Titel: | Die Metrische Dimension spezieller Graphklassen | |||||||
| Weiterer Titel: | The Metric Dimension of special graph classes | |||||||
| URL für Lesezeichen: | https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=52797 | |||||||
| URN (NBN): | urn:nbn:de:hbz:061-20200420-110943-4 | |||||||
| Kollektion: | Dissertationen | |||||||
| Sprache: | Deutsch | |||||||
| Dokumententyp: | Wissenschaftliche Abschlussarbeiten » Dissertation | |||||||
| Medientyp: | Text | |||||||
| Autor: | Vietz, Duygu [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: | Der Entwurf effizienter Algorithmen für Graphenprobleme spielt in der Informatik eine zentrale Rolle. Viele interessante Probleme lassen sich jedoch nicht effizient für allgemeine Graphen lösen. Oft können gewisse Eigenschaften in der Struktur bestimmter Graphklassen genutzt werden, um solche Probleme effizient, das heißt in polynomieller Zeit, für diese Graphklassen zu lösen. Das Problem „Metrische Dimension“ ist ein solches NP-schweres Problem. Es wurde von Slater (1975) und Harary und Melter (1976) unabhängig voneinander eingeführt. Für einen ungerichteten Graphen G=(V,E) mit einer Knotenmenge V und einer Kantenmenge E ist eine trennende Menge eine Teilmenge R der Knotenmenge V, sodass für jedes Knotenpaar u,v ein Knoten r aus R existiert, sodass d(u,r) ungleich d(v,r) ist. Dabei bezeichnet d(u,v) die Länge eines kürzesten Weges zwischen den Knoten u und v in dem Graphen G. Die metrische Dimension von G ist die Größe einer kleinsten trennenden Menge für G und wird mit mdim(G) bezeichnet. Das Problem „Metrische Dimension“ ist die Entscheidung, ob mdim(G) höchstens k ist für einen ungerichteten Graphen G und eine natürliche Zahl k.
Seit der Einführung dieses Problems wurden viele Ergebnisse über die Komplexität der „Metrischen Dimension“ für verschiedene bekannte Graphklassen, wie Bäume, bipartite Graphen, planare Graphen, außenplanare Graphen, Cographen, Wheels, Intervallgraphen und viele weitere veröffentlicht. Die Ergebnisse umfassen sowohl NP-Vollständigkeitsbeweise als auch effiziente Algorithmen. Aus der Problemstellung „Metrische Dimension“ sind weitere Varianten entstanden, die unter anderem durch praktische Fragestellungen motiviert sind. Zu diesen Varianten gehören die „Gewichtete Metrische Dimension“, die „Lokale Metrische Dimension“, die „Adjazenzdimension“, die „Starke Metrische Dimension“, die „Fehlertolerante Metrische Dimension“ und viele weitere. Auch diese Problemvarianten wurden in vielen verschieden Publikationen analysiert. Die vorliegende Arbeit leistet einen Beitrag zu diesem Themengebiet. Nach einer Einführung in die Grundlagen und den aktuellen Stand der Forschung in den Kapiteln 1 bis 3, folgt in Kapitel 4 ein Algorithmus, der eine baumstrukturierte Dekomposition eines Graphen durchführt und anhand dieser Zerlegung die metrische Dimension des Graphen bestimmt. In Kapitel 5 wird ein Linearzeitalgorithmus zur Bestimmung der gewichteten fehlertoleranten metrischen Dimension von Co-Graphen vorgestellt. Kapitel 6 zeigt einen NP-Vollständigkeitsbeweis für das Problem „Lokale Metrische Dimension“ für planare Graphen. Kapitel 7 führt in die Klasse der sogenannten „Sonnengraphen“ ein. Es wird ein effizienter Algorithmus zur Bestimmung der gewichteten metrischen Dimension und der fehlertoleranten metrischen Dimension von Sonnengraphen vorgestellt. In Kapitel 8 wird ein effizienter Algorithmus zur Bestimmung der fehlertoleranten metrischen Dimension von Wheels präsentiert. Abschließend wird die starke metrische Dimension in Hinblick auf die praktische Anwendung beim Routing in Sensornetzwerken diskutiert.The design of efficient algorithms for graph theoretical problems plays an important role in the field of computer science. However, many problems are not efficiently solvable for general graphs. Sometimes such problems can be solved efficiently on some restricted graph classes by considering their specific properties. The problem "Metric Dimension" is such an NP-hard problem. It was introduced independently by Slater (1975) and Harary and Melter (1976). For an undirected graph G=(V,E) with vertex set V and edge set E a subset of vertices R is called a resolving set, if for every vertex pair u,v there is a vertex r in R with d(u,r) not equal to d(v,r). With d(u,v) we denote the length of a shortest path between u and v in G. The metric dimension of G is the size of a smallest resolving set for G and is denoted by mdim(G). The problem "Metric Dimension" is to decide if mdim(G) is at most k for an undirected graph G and a positive integer k. Many papers concerning the complexity of "Metric Dimension" for several different graph classes have been published since the first introduction of this problem. These include graph classes such as trees, bipartite graphs, planar graphs, outerplanar graphs, cographs, wheels, interval graphs and many more. In fact, some were shown to be NP-hard, for others efficient algorithms were given. The analysis of the "Metric Dimension" problem lead to further variants, such as the "Weighted Metric Dimension", the "Local Metric Dimension", the "Adjacency Dimension", the "Strong Metric Dimension", the "Fault-tolerant Metric Dimension" and many more. All of these variants have been discussed in various publications. This doctoral thesis contributs to this field of study. In chapters 1 to 3 it first gives an introduction into graph theoretical basics and the state of research. Chapter 4 presents an algorithm which performs a tree-structured decompositon of a graph that can be used to determine the metric dimension of the graph. Chapter 5 describes a linear time algorithm to determine the weighted fault-tolerant metric dimension of a cograph. Chapter 6 proves the NP-completeness of the problem "Local Metric Dimension" for planar graphs. Chapter 7 introduces the class of so-called "sun graphs" and gives an efficient algorithm for the computation of their weighted metric dimension and fault-tolerant metric dimension. Chapter 8 presents an efficient algorithm to determine the fault-tolerant metric dimension of wheels. Finally we discuss some properties of the strong metric dimension focusing on the routing in sensor networks. | |||||||
| Lizenz: |  Urheberrechtsschutz | |||||||
| Fachbereich / Einrichtung: | Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Algorithmen und ihre Anwendungen | |||||||
| Dokument erstellt am: | 20.04.2020 | |||||||
| Dateien geändert am: | 20.04.2020 | |||||||
| Promotionsantrag am: | 28.01.2020 | |||||||
| Datum der Promotion: | 13.03.2020 |
