2015
Aachen, Techn. Hochsch., Diss., 2015
Genehmigende Fakultät
Fak01
Hauptberichter/Gutachter
;
Tag der mündlichen Prüfung/Habilitation
2015-04-17
Online
URN: urn:nbn:de:hbz:82-rwth-2015-018231
URL: https://publications.rwth-aachen.de/record/465864/files/465864.pdf
URL: https://publications.rwth-aachen.de/record/465864/files/465864.pdf?subformat=pdfa
Einrichtungen
Inhaltliche Beschreibung (Schlagwörter)
Mathematik (frei) ; Graphentheorie (frei) ; Unabhängigkeit (frei) ; Gradsequenz (frei) ; graph theory (frei) ; independence (frei) ; degree seqeuence (frei)
Thematische Einordnung (Klassifikation)
DDC: 510
Kurzfassung
Die Unabhängigkeitszahl eines Graphen ist die Mächtigkeit einer maximalen unabhängigen Menge, d.h. eine Menge aus Knoten, die paarweise nicht miteinander verbunden sind. Für manche spezielle Graphen ist die Unabhängigkeitszahl leicht zu berechnen. Im Allgemeinen gibt es aber keinen effizienten Algorithmus, der diese Invariante in angemessener Zeit berechnet und bildet somit ein fundamentales Problem in der Graphentheorie. Die Bestimmung der Unabängigkeitszahl für allgemeine Graphen ist ein NP-schweres Problem. Neben dem mathematischen Interesse findet die Unabhängigkeitszahl auch in vielen wissenschaftlichen und wirtschaftlichen Problemen ihre Anwendung. Dabei steht die genaue Berechnung solcher Paramter nicht im Vordergrund. Meistens reicht es eine Schranke anzugeben um zu entscheiden, ob ein Prozess durchführbar ist oder nicht. Darin liegt die Motivation, weitere Approximationen für die Unabhängigkeitszahl zu finden und existierende Schranken zu verbessern. Die Approximation der Unabhängigkeitszahl hat den Vorteil, dass nicht alle Informationen eines Graphen benötigt werden. Oft leiten sich die Schranken aus verschiedenen Parametern ab, die einfacher zu handhaben sind. In der vorliegenden Arbeit richten wir den Fokus auf Schranken, die sich aus der Gradsequenz eines Graphen berechnen. Wir haben weiterführende Erkenntnisse über bekannte Schranken und Algorithmen gewonnnen. Dabei lag unser Schwerpunkt bei der Schranke von Owen Murphy aus dem Jahr 1991. Wir haben das Verfahren für spezielle Graphentypen modifiziert und verbessert. Basierend auf dem Murphy Algorithmus haben wir eine neue untere Schranke für die k-Unabhängigkeitszahl entwickelt, welche eine Verallgemeinerung der Unabhängigkeitszahl darstellt. Es gibt Graphen die zeigen, dass unsere neue Approximation in gewissen Fällen eine Verbesserung aller bekannten Schranken ist. Motiviert durch den berühmten Satz von Paul Turán haben wir ein Problem der extremalen Graphentheorie gelöst. Unsere Formel macht eine Aussage über die minimale Anzahl von Kanten, die ein Graph mit gegebener Knotenzahl und k-Unabhängigkeitszahl haben kann. Bei diesen Untersuchungen haben wir einen weiteren Ansatz gefunden, wie man den Algorithmus von Murphy auf k-unabhängige Mengen verallgemeinern kann. Dies führte zu einer zweiten neuen Schranke für bestimmte Graphenklassen, die auch hier zu einer Verbesserung aller bekannten Schranken führte. In Erweiterung unserer Ergebnisse stellt sich in diesem Zusammenhang das Problem, die neue Schranke für allgemeine Graphen zu beweisen. Weder ein Beweis noch ein Gegenbeispiel haben wir fürunsere Hypothese gefunden, so dass die vorliegende Dissertation mit einer Vermutungabschließt.The independence number of a graph is the cardinality of a largest set of vertices such that no two vertices in the set are connected by an edge. The problem of determining a maximum independent set is a fundamental problem in graph theory. Since it is NP-hard for most classes of graphs, approximations in form of lower and upper bounds on the independence number are of specific interest. In addition to the strictly mathematical point of view this graphical invariant appears in several economic and scientific applications. With an appropriate reformulation some practical problems can be interpreted as graphs or networks. The approximation of the decision variables can be sufficient to decide whether a process is feasible or not. Hence the motivation is to investigate further approximations and to improve bounds on the independence number and the generalized k-independence number. The advantage of approximation algorithms is, they do not need all information of a given graph or network. The results often derive from parameters like the order or size of the graph. In this thesis our focus lies on the relation between the independence number and the degree sequence. We have gained many new insights from given results. We modified an algorithm found by Owen Murphy in 1991. This leads to an improvement for graphs which satisfied certain properties and still guarantees a lower bound on the independence number. Our main result is a new lower bound on the k-independence number based on Murphy’s algorithm. For some graphs, our new bound gives a genuine improvement over all known tractable bounds. Motivated by Paul Turàn’s famous theorem, we solved an extremal problem for graphs. Our result makes statements about the minimum size of a graph with given order and k-independence number. It is these considerations which have led to another new lower bound on the k-independence number only under certain conditions. We present graphs for which our result is an improvement over all known bounds. Neither a proof nor a counterexample was found that this result is a bound for arbitrary graphs. Thus we closed our work with a conjecture.
OpenAccess:
PDF PDF (PDFA)
(additional files)
Dokumenttyp
Dissertation / PhD Thesis
Format
online, print
Sprache
English
Externe Identnummern
HBZ: HT018631389
Interne Identnummern
RWTH-2015-01823
Datensatz-ID: 465864
Beteiligte Länder
Germany