Refine
Document Type
- Doctoral thesis (2)
Has Fulltext
- yes (2)
Is part of the Bibliography
- no (2)
Keywords
- Graphentheorie (2) (remove)
Institute
Vertex and edge orderings of graphs are commonly used in algorithmic graph theory. Such orderings can encode structural properties of graphs in a condensed way and, thus, they can be used to process a graph efficiently. A common approach to find particular vertex orderings are graph searches. Here, we study the complexity of deciding whether vertex orderings with special properties can be found by particular graph searches. The properties of these orderings concern their end-vertices, their search trees or constraints encoded by partial orders.
Many graph classes can be characterized via special vertex orderings. We introduce another example, the semi-proper interval graphs, generalizations of connected proper interval graphs that are characterized via special variants of perfect elimination orderings. We study the structure of these graphs, present a linear-time recognition algorithm and show that they share some strong properties on Hamiltonian paths and cycles with proper interval graphs.
We also generalize the notion of graph classes to the case of edge-weighted graphs. A weighted graph is a member of such a weighted class if subgraphs containing edges of particular weights are members of the respective unweighted graph class. We present conditions on an unweighted graph class that ensure a linear-time recognition algorithm for its corresponding weighted graph class. This conditions make use of a novel edge monotonicity and of particular edge orderings. We apply this result to three well-known graph classes, namely split graphs, threshold graphs, and chain graphs.
Finally, we consider dynamic algorithms on threshold and chain graphs. These algorithms update certain properties of a graph after small modifications are applied to its vertex or edge set. We present certifying dynamic recognition algorithms of these classes, i.e., if the graph leaves the class after the modification, we can prove this by providing a forbidden induced subgraph of bounded size. Building on these results, we extend the notion of dynamic recognition algorithms to whole sets of edges and vertices. Furthermore, we present dynamic algorithms for the Hamiltonian path and cycle problems.
Dem Moment der Vorhersage kommt eine zentrale Rolle innerhalb der Konzepte der ökologischen Modellierung zu. Flächendeckende Information ist durch die gegenwärtigen Möglichkeiten der Fernerkundung auf die integrative Charakterisierung von größeren Ausschnitten der Landschaft beschränkt, eine Ermittlung einzelner Arten oder Lebensgemeinschaften ist nicht sinnvoll möglich. Deshalb werden Ausschnitte der Landschaft in Form mehr oder weniger repräsentativer Untersuchungsflächen intensiv untersucht und durch Interpolation/ Extrapolation oder Analogieschluss auf den Rest der Landschaft geschlossen. Die Verwendung z. T. hochkomplexer statistischer Modelle, die einen vom Beobachter bestimmten Ausschnitt aus allen verfügbaren Eigenschaften der Landschaft bzw. der Umwelt der Organismen als Parameter verrechnen, ist die gängige Praxis in der Modellierung. Im Zusammenwirken von punktueller Erfassung der Zielorganismen, (Satelliten-)Fernerkundung, Autökologie und Statistik entsteht ein Abbild der Wirklichkeit als Modell, das in jedem Verarbeitungsschritt (insbesondere in den Interpretationsschritten) Fehler und Unsicherheiten erzeugt, fortschreibt und/oder potenziert. Diese Fehlerfortschreibung und –vergrößerung wird vermieden, je einfacher die Modelle sind, wobei gleichzeitig eine Einbeziehung verfügbarer und wahrscheinlich wichtiger Information unterbleibt, so dass von Seiten des Modellierers eine Abwägung vorzunehmen ist, ob einfache und weniger fehlerbehaftete oder aber komplexe und fehlerbehaftete Modelle vorzuziehen sind. In der vorliegenden Auswahl wurden die einfachen Modelle bevorzugt. Auf 158 Probeflächen in Südost-Brandenburg (Spree-Neiße-Kreis, Stadt Cottbus, Landkreis Dahme-Spreewald, Landkreis Oberspreewald-Lausitz) wurden 37 Heuschreckenarten mit Frequenzen zwischen 0,6 und 99,4 % nachgewiesen, sowie die Aktivität von 49 Libellenarten mit Frequenzen zwischen 0,6 und 74,1 % dokumentiert. Die Beobachtungsdaten wurden verwendet, um mit Hilfe einfacher graphenbasierter topographischer Modelle Vorhersagen über das Vorkommen von Arten zu machen. Als Modelle wurden Delaunay-Triangulationen, Gabriel-Graphen, Minimal spannende Bäume, Graphen über die nächsten Nachbarn, sowie Voronoi-Diagramme verwendet. Außerdem wurde mit Hilfe der Methode des ‚leave-one-out’ über einige Graphen ‚modellierte Beobachtungen’ berechnet. Zum Modellvergleich wurden alle Modelle gegen alle anderen unter Einbeziehung der Beobachtungen und der ‚modellierten Beobachtungen’ hinsichtlich der Korrelation der Arten-Vektoren paarweise gegenübergestellt. Dabei ist deutlich geworden, dass es Modellpaare gibt, sehr hoch miteinander korreliert sind. Es wurde geprüft, ob die Korrelationen von der Anzahl der Nachbarn, der Relation der Zahlen der unbekannten zu den Zahlen der bekannten Nachbarn, oder der Wichtung der einzelnen Nachbarn, oder den Distanzen der Nachbarn voneinander abhängig sind. Solche Abhängigkeiten treten schwach oder gar nicht in Erscheinung. Es ist ersichtlich, dass sowohl die Konstruktion der Graphen (d. h. die Wahl des Modells), als auch die Struktur des Graphen mit den untersuchten Flächen als Knoten einen Einfluss auf die Übereinstimmung der Vorhersageergebnisse nimmt. Zur Vorhersagegüte wird die gängige Praxis, die Vorhersage des verwendeten Modells an den zugrunde liegenden Beobachtungen zu messen, grundsätzlich kritisiert, da der Modellcharakter der Beobachtungen nicht ausreichend reflektiert und die Beobachtungen von unbekannter Güte sind. Es wird daher vorgeschlagen, die in dieser Untersuchung verglichenen Modelle mit den adäquaten ‚modellierten Beobachtungen’ als Maßstab der Vorhersagegüte zu vergleichen. Aus diesem und anderen Gründen werden die Voronoi-Diagramme bzw. die dazu dualen Delaunay-Triangulationen als ‚beste Modelle’ herausgestellt, wobei die ähnlichen Gabriel-Graphen eine vergleichbare Güte erreichen können.