scientific article; zbMATH DE number 1312888

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

Aus der Einleitung der Dissertation: Die vorliegende Arbeit ist in zwei Teile gegliedert. Der erste Teil umfaßt die Kapitel 1 und 2. Er beinhaltet als zentrales Ergebnis in Abschnitt 2.3 einen linearen Algorithmus für die homogene Dekomposition. Dieser Algorithmus baut auf den bekannten linearen Algorithmen für die modulare Dekomposition auf. Kapitel 1 enthält die grundlegenden Definitionen und trifft die Vorbereitungen für das Verständnis des Unterschieds zwischen homogener Dekomposition und modularer Dekomposition. In Abschnitt 2.1 wird dann gezeigt, dass sich eine Vorstufe der homogenen Dekomposition, die wir als medievale Dekomposition bezeichnen, nur unwesentlich von der modularen Dekomposition unterscheidet. Grundlage für die lineare homogene Dekomposition ist die Anwendung eines Satzes über Splitgraphen von Hammer und Simeone. In Abschnitt 2.2 ist eine Prozedur angegeben, die es uns ermöglicht, diesen Satz auf das Ergebnis der Algorithmen zur modularen Dekomposition anzuwenden. Man beachte, dass wir mit der homogenen Dekomposition eines Graphen \(G\) unmittelbar die die \(p\)-Zusammenhangskomponenten von \(G\) erhalten. Folglich ist auch das Berechnen der \(p\)-Zusammenhangskomponenten eines beliebigen Graphen in Linearzeit möglich. Aus diesem Grund verallgemeinert unser Algorithmus die bisher bekannten linearen Erkennungsalgorithmen für Kographen, \(P_4\)-reducible, \(P_4\)-sparse und \(P_4\)-extendible Graphen. Außerdem ist er die Grundlage der oben erwähnten linearen Algorithmen für Probleme auf \((q,q-4)\)- und \((q,q-3)\)-Graphen. Im zweiten Teil der Arbeit beschäftigen wir uns mit Graphen, die wenige induzierte \(P_4\)s enthalten, insbesondere mit den \((q,q-2)\)-Graphen für \(q\geq 8\). Dabei ist zu beachten, dass nach Babel für \((q,q-2)\)-Graphen mit \(q\leq 7\) das Isomorphieproblem polynomial-äquivalent zum allgemeinen Isomorphieproblem ist. Daher ist nicht zu erwarten, dass die \(p\)-Zusammenhangskomponenten von \((q,q-2)\)-Graphen für \(q\leq 7\) eine einfache Struktur haben. Kapitel 3 liefert eine Übersicht über alle bisher untersuchten Graphen mit wenigen \(P_4\)s. In Abschnitt 3.5 wird gezeigt, dass die \(p\)-Zusammenhangskomponenten von \((q,q-2)\)-Graphen mit \(q\geq 8\), bis auf \(p\)-Komponenten mit weniger als \(q\) Knoten, \((8,6)\)-Graphen sind. In Kapitel 4 wird dann eine vollständige Charakterisierung der \(p\)-zusammenhängenden \((8,6)\)-Graphen mit mindestens 8 Knoten durchgeführt. Dies wird durch eine sehr umfangreiche Fallunterscheidung nach gewissen induzierten Teilgraphen erreicht. Diese Teilgraphen sind die sehnenlosen Kreise mit mehr als 8 Knoten und deren Komplemente, spezielle sogenannte einfache \(p\)-Ketten und gewisse einfach strukturierte Splitgraphen, die man als Spider bezeichnet. Im abschließenden Kapitel 5 wird schließlich gezeigt, dass die Erkennung, das Testen von Isomorphie, sowie das Lösen der Standardoptimierungsprobleme für \((8,6)\)-Graphen mit linearem Zeitaufwand möglich ist. Da die \((8,6)\)-Graphen die Kographen, die \(P_4\)-reducible, die \(P_4\)-lite und die \(P_4\)-extendible, die \(P_4\)-sparse, die \(P_4\)-tidy Graphen sowie die \(p\)-Bäume enthalten, verallgemeinert diese Arbeit viele der angesprochenen Ergebnisse.

Recommendations

Cited in

(1)

Almost tight upper bounds for vertical decompositions in four dimensions

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4254865)