Linear Extension Graphs and Linear Extension Diameter (Tienda española)

Previo

Indice, Datei (39 KB)
Lectura de prueba, Datei (120 KB)

Die Dissertation „Linear Extension Graphs and Linear Extension Diameter“ von Mareike Massow untersucht die strukturellen und algorithmischen Eigenschaften linearer Erweiterungen endlicher partiell geordneter Mengen. Im Mittelpunkt stehen lineare Erweiterungsgraphen, deren Knoten sämtliche linearen Erweiterungen einer Halbordnung repräsentieren und deren Kanten durch die Vertauschung benachbarter unvergleichbarer Elemente entstehen. Die Arbeit analysiert, inwieweit sich die Eigenschaften einer Halbordnung aus ihrem linearen Erweiterungsgraphen rekonstruieren lassen. Mithilfe der modularen Graphzerlegung entwickelt die Autorin ein Verfahren zur Rekonstruktion entsprechender Halbordnungen und zur Erkennung linearer Erweiterungsgraphen. Ein weiterer Schwerpunkt liegt auf dem linearen Erweiterungsdurchmesser, der die maximale Anzahl unterschiedlich angeordneter Elementpaare zwischen zwei linearen Erweiterungen beschreibt. Es wird bewiesen, dass die Entscheidung über einen vorgegebenen Mindestdurchmesser für allgemeine Halbordnungen NP-vollständig ist, während für Halbordnungen der Breite drei ein polynomialer Algorithmus existiert. Darüber hinaus werden exakte Ergebnisse für boolesche und distributive Verbände hergeleitet und diametrale Paare linearer Erweiterungen charakterisiert. Abschließend untersucht die Dissertation sogenannte diametral umkehrende Halbordnungen und widerlegt eine bestehende Vermutung durch ein Gegenbeispiel. Die Ergebnisse erweitern die mathematischen Grundlagen der Ordnungstheorie, Graphentheorie und algorithmischen Kombinatorik.