The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 80 of 612
Back to Result List

Ready to order? : on vertex and edge orderings of graphs

Ready to order? : über Knoten- und Kantenordnungen von Graphen

  • 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 graphVertex 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.show moreshow less
  • Knoten- und Kantenordnungen von Graphen werden häufig in der algorithmischen Graphentheorie verwendet. Solche Ordnungen können Eigenschaften von Graphen in komprimierter Form kodieren und können damit zur effizienten Verarbeitung eines Graphen verwendet werden. Ein gängiger Ansatz, um bestimmte Knotenordnungen zu finden, sind Graphensuchen. Wir untersuchen hier wie schwer es ist zu entscheiden, ob Knotenordnungen mit speziellen Eigenschaften durch bestimmte Graphensuchen gefunden werden können. Die Eigenschaften dieser Ordnungen betreffen ihre Endknoten, ihre Suchbäume oder Einschränkungen, die durch partielle Ordnungen gegeben sind. Viele Graphenklassen lassen sich durch spezielle Knotenordnungen charakterisieren. Wir stellen ein weiteres Beispiel vor, die Semi-Proper-Intervallgraphen, Verallgemeinerungen von zusammenhängenden Proper-Intervallgraphen, die durch spezielle Varianten perfekter Eliminationsordnungen charakterisiert sind. Wir untersuchen die Struktur dieser Graphen, stellen einen Linearzeit-Erkennungsalgorithmus vor undKnoten- und Kantenordnungen von Graphen werden häufig in der algorithmischen Graphentheorie verwendet. Solche Ordnungen können Eigenschaften von Graphen in komprimierter Form kodieren und können damit zur effizienten Verarbeitung eines Graphen verwendet werden. Ein gängiger Ansatz, um bestimmte Knotenordnungen zu finden, sind Graphensuchen. Wir untersuchen hier wie schwer es ist zu entscheiden, ob Knotenordnungen mit speziellen Eigenschaften durch bestimmte Graphensuchen gefunden werden können. Die Eigenschaften dieser Ordnungen betreffen ihre Endknoten, ihre Suchbäume oder Einschränkungen, die durch partielle Ordnungen gegeben sind. Viele Graphenklassen lassen sich durch spezielle Knotenordnungen charakterisieren. Wir stellen ein weiteres Beispiel vor, die Semi-Proper-Intervallgraphen, Verallgemeinerungen von zusammenhängenden Proper-Intervallgraphen, die durch spezielle Varianten perfekter Eliminationsordnungen charakterisiert sind. Wir untersuchen die Struktur dieser Graphen, stellen einen Linearzeit-Erkennungsalgorithmus vor und zeigen, dass sie einige starke Eigenschaften in Bezug auf Hamiltonpfade und -kreise mit Proper-Intervallgraphen teilen. Wir verallgemeinern auch den Begriff der Graphenklassen auf den Fall von Graphen mit gewichteten Kanten. Ein gewichteter Graph ist Element einer solchen gewichteten Klasse, wenn Untergraphen mit Kanten bestimmter Gewichte Elemente der jeweiligen ungewichteten Graphenklasse sind. Wir präsentieren Bedingungen für eine ungewichtete Graphenklasse, die einen Erkennungsalgorithmus mit linearer Laufzeit für die entsprechende gewichtete Graphenklasse sicherstellen. Diese Bedingungen nutzen eine neuartige Monotonieeigenschaft und spezielle Kantenordnungen. Diese Ergebnisse wenden wir auf drei bekannte Graphenklassen an: Split-Graphen, Threshold-Graphen und Chain-Graphen. Am Ende betrachten wir dynamische Algorithmen für Threshold- und Chain-Graphen. Diese Algorithmen aktualisieren bestimmte Eigenschaften eines Graphen, nachdem kleinere Änderungen an seiner Knoten- oder Kantenmenge vorgenommen wurden. Wir stellen zertifizierende dynamische Erkennungsalgorithmen für diese Klassen vor, das heißt falls der Graph die Klasse nach der Modifikation verlässt, können wir dies mit einem verbotenen induzierten Untergraphen von beschränkter Größe beweisen. Aufbauend auf diesen Ergebnissen erweitern wir den Begriff der dynamischen Erkennungsalgorithmen auf ganze Mengen von Kanten und Knoten. Außerdem stellen wir dynamische Algorithmen für das Hamiltonpfad- und das Hamiltonkreis-Problem vor.show moreshow less

Download full text files

Export metadata

Additional Services

Search Google Scholar Stastistics
Metadaten
Author: Robert SchefflerORCiD
URN:urn:nbn:de:kobv:co1-opus4-63019
DOI:https://doi.org/10.26127/BTUOpen-6301
Referee / Advisor:Prof. Dr. Ekkehard Köhler, Prof. Dr. Feodor F. DraganORCiD, Prof. Dr. Christophe PaulORCiD
Document Type:Doctoral thesis
Language:English
Year of Completion:2023
Date of final exam:2023/03/07
Release Date:2023/04/11
Tag:Dynamischer Algorithmus; Gewichteter Graph; Graphensuche; Kantenordnung; Knotenordnung
Dynamic algorithm; Edge ordering; Graph search; Vertex ordering; Weighted graph
GND Keyword:Graphentheorie; Graphenklasse
Institutes:Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Diskrete Mathematik und Grundlagen der Informatik
Licence (German):Keine Lizenz vergeben. Es gilt das deutsche Urheberrecht.
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.