In this thesis, we look at a well-known connection between the graph coloring problem and the solvability of certain systems of polynomial equations. In particular, we examine the connection between the structure of a graph and the structure of the Gröbner bases of the graph’s coloring ideal.
From a theoretical viewpoint, we show some properties of such Gröbner bases, and we develop a polynomial-time algorithm to compute a Gröbner basis for chordal graphs. From the experimental side, we state results about specific Gröbner bases and about the Gröbner fan for a variety of graph families. Moreover, some heuristics and techniques are explored that reduce the computational complexity.
The relevance of heuristic methods is justified by a section about expected intrinsic hardness of Gröbner basis computations.
Translation of the title:
Über die Struktur von Gröbnerbasen für Graphenfärbungsideale
(German)
Translation of the abstract:
In dieser Arbeit betrachten wir die Verbindung zwischen dem Graphenfärbungsproblem und der Lösbarkeit bestimmter polynomieller Gleichungssysteme. Im Speziellen untersuchen wir den Zusammenhang zwischen der Struktur eines Graphen und der Struktur der Gröbnerbasen des zugehörigen Färbungsideals.
Wir zeigen einige Eigenschaften solcher Gröbnerbasen auf und konstruieren einen Algorithmus, der in polynomieller Zeit eine Gröbnerbasis für chordale Graphen erzeugt. Daneben zeigen wir spezifische Gröbnerbasen für einige Familien von Graphen, und treffen Aussagen über ihre Komplexität sowie Eigenschaften der zugehörigen Gröbnerfächer. Außerdem untersuchen wir einige Heuristiken, die dazu geeignet sind, den Rechenaufwand der verwendeten Algorithmen zu senken.
In einem Kapitel über die intrinsische Komplexität der Berechnung von Gröbnerbasen rechtfertigen wir die Relevanz heuristischer Methoden und der Betrachtung von Spezialfällen.
(German)
Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.
Dieser Datensatz wurde nicht während einer Tätigkeit an der Universität Mannheim veröffentlicht, dies ist eine Externe Publikation.
Creative Commons Attribution 4.0 International (CC BY 4.0)
Search Authors in
