TY - THES A1 - Beisegel, Jesse T1 - Convexity in graphs: vertex order characterisations and graph searching T1 - Konvexität in Graphen: lineare Knotenordnungen und Graphensuchen N2 - We study convexities designed to characterise some of the most fundamental classes of graphs. To this end, we present some known results on this topic in a slightly different form, so as to give a homogeneous representation of a very disparate field. Furthermore, we present some new results on the Caratheodory number of interval graphs and also give a more or less exhaustive account of everything that is known in this context on AT-free graphs, including new results on characterising linear vertex orders and the structure of the intervals of this class. We introduce the new class of bilateral AT-free graphs which is motivated by the linear order characterisation and the convexity used to describe AT-free graphs. We discuss their relation to other known classes and consider the complexity of recognition. Furthermore, as a consequence of notions from abstract convexity we present algorithmic results with regards to some natural subclasses of these. As an application of notion of an extreme vertex of a convex geometry, we discuss structural aspects of avoidable vertices in graphs, which form a generalisation of simplicial vertices. This includes a characterisation of avoidable vertices as simplicial vertices in some minimal triangulation of the graph and a new proof of the existence result. Furthermore, we discuss the algorithmic issues regarding the problem of efficient computation of avoidable vertices in a given graph. This is complemented by an algorithmic application of the concept of avoidable vertices to the maximum weight clique problem, by identifying a rather general class of graphs in which every avoidable vertex is bisimplicial. This leads to a polynomial-time algorithm for the maximum weight clique problem in this class of graphs. Implications of this approach for digraphs are also discussed. All of these results lead to a conjecture concerning the generalisation of avoidable vertices to avoidable paths and we prove this conjecture for paths of length less or equal to two. Finally, we analyse the properties of many different and widely used forms of graph search. Here, we discuss the problem of recognising whether a given vertex can be the last vertex visited by some fixed graph search. Moreover, we present some new aspects of the problem of deciding whether a given spanning tree of a graph is a graph search tree of a particular type of search. We generalise the concept of such trees to many well-known searches and give a broad analysis of the computational complexity of this problem. Both of these discussions are motivated by the use of graph searches in the context of computing properties of convexity. N2 - In dieser Arbeit betrachten wir Konvexitäten, die entworfen wurden, um einige der grundlegendsten Graphenklassen zu charakterisieren. Dazu präsentieren wir einige bekannte Resultate zu diesem Thema in einer abgeänderten Form, um eine homogene Darstellung eines diversen Felds zu bieten. Außerdem, geben wir neue Resultate über die Caratheodory Zahl von Intervallgraphen, sowie einen weitestgehend vollständigen Überblick über alle Ergebnisse bezüglich der charakterisierenden Konvexität von AT-freien Graphen, welcher auch neue Ergebnisse über charakterisierende Knotenordnungen und die Struktur der Intervalle dieser Klasse umfasst. Wir führen die neue Klasse der bilateral AT-freien Graphen ein, welche durch die charakterisierende Knotenordnung und Konvexität der AT-freien Graphen motiviert ist. Wir diskutieren das Verhältnis dieser Graphen zu anderen Unterklassen der AT-freien Graphen und untersuchen die Komplexität ihrer Erkennung. Außerdem geben wir einige algorithmische Ergebnisse zu Unterklassen von bilateral AT-freien Graphen, welche aus der Analyse ihrer Konvexität folgen. Als Anwendung des Begriffs eines Extremknoten einer konvexen Geometrie diskutieren wir einige strukturelle Aspekte von vermeidbaren Knoten, welche eine Verallgemeinerung der simplizialen Knoten darstellen. Dies beinhaltet eine Charakterisierung von vermeidbaren Knoten als simpliziale Knoten einer minimalen Triangulierung eines Graphen, sowie einen neuen Beweis über deren Existenz. Wir analysieren die algorithmischen Aspekte des Erkennungsproblems von vermeidbaren Knoten eines gegebenen Graphen. Diese Ergebnisse verwenden wir, um das Konzept eines vermeidbaren Knotens zur Berechnung von Cliquen maximalen Gewichts algorithmisch auszunutzen, indem eine Klasse ermittelt wird, für die jeder vermeidbare Knoten bisimplizial ist. Dies führt zu einem Polynomialzeitalgorithmus zur Berechnung einer Clique maximalen Gewichts auf dieser Klasse. Die Konsequenzen dieses Ansatzes werden auch für gerichtete Graphen analysiert. Alle diese Ergebnisse geben den Anlass zu einer Vermutung, die die Existenz vermeidbarer Knoten zu der Existenz vermeidbarer Pfade ausweitet; diese Vermutung wird für Pfade der Länge 1 und 2 bewiesen. Schließlich betrachten wir die Eigenschaften einiger unterschiedlicher und häufig genutzter Graphensuchen. Wir diskutieren das Problem der Erkennung von Endknoten dieser Suchen. Außerdem präsentieren wir neue Ergebnisse über die Erkennung von Suchbäumen verschiedener Graphensuchen. Wir verallgemeinern das Konzept solcher Suchbäume, um weitere komplexere Suchstrategien abzufangen, und betrachten die Komplexität der Erkennung solcher Bäume. Diese Untersuchungen sind motiviert durch die häufige Verwendung von Graphensuchen, um Eigenschaften von Konvexitäten algorithmisch zu ermitteln. KW - Graph convexity KW - Convex geometry KW - Graph searching KW - Vertex order characterisation KW - Asteroidal triples KW - Asteroidale Tripel KW - Lineare Knotenordnung KW - Graphensuche KW - Konvexe Geometrie KW - Konvexität KW - Graph KW - Konvexität KW - Konvexe Geometrie Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-51452 ER - TY - THES A1 - Scheffler, Robert T1 - Ready to order? : on vertex and edge orderings of graphs T1 - Ready to order? : über Knoten- und Kantenordnungen von Graphen N2 - 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. N2 - 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 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. KW - Graph search KW - Graphensuche KW - Dynamic algorithm KW - Dynamischer Algorithmus KW - Edge ordering KW - Kantenordnung KW - Vertex ordering KW - Knotenordnung KW - Weighted graph KW - Gewichteter Graph KW - Graphentheorie KW - Graphenklasse Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-63019 ER - TY - THES A1 - Strehler, Martin T1 - Signalized flows - optimizing traffic signals and guideposts and related network flow problems T1 - Signalisierte Netzwerkflüsse - Optimierung von Lichtsignalanlagen und Vorwegweisern und daraus resultierende Netzwerkflussprobleme N2 - Guideposts and traffic signals are important devices for controlling inner-city traffic and their optimized operation is essential for efficient traffic flow without congestion. In this thesis, we develop a mathematical model for guideposts and traffic signals in the context of network flow theory. Guideposts lead to confluent flows where each node in the network may have at most one outgoing flow-carrying arc. The complexity of finding maximum confluent flows is studied and several polynomial time algorithms for special graph classes are developed. For traffic signal optimization, a cyclically time-expanded model is suggested which provides the possibility of the simultaneous optimization of offsets and traffic assignment. Thus, the influence of offsets on travel times can be accounted directly. The potential of the presented approach is demonstrated by simulation of real-world instances. N2 - Vorwegweiser und Lichtsignalanlagen sind wichtige Elemente zur Steuerung innerstädtischen Verkehrs und ihre optimale Nutzung ist von entscheidender Bedeutung für einen staufreien Verkehrsfluss. In dieser Arbeit werden Vorwegweiser und Lichtsignalanlagen mittels der Netzwerkflusstheorie mathematisch modelliert. Vorwegweiser führen dabei zu konfluenten Flüssen, bei denen Fluss einen Knoten des Netzwerks nur gebündelt auf einer einzigen Kante verlassen darf. Diese konfluenten Flüsse werden hinsichtlich ihrer Komplexität untersucht und es werden Polynomialzeitalgorithmen für das Finden maximaler Flüsse auf ausgewählten Graphenklassen vorgestellt. Für die Versatzzeitoptimierung von Lichtsignalanlagen wird ein zyklisch zeitexpandiertes Modell entwickelt, das die gleichzeitige Optimierung der Verkehrsumlegung ermöglicht. So kann der Einfluss geänderter Versatzzeiten auf die Fahrzeiten direkt berücksichtigt werden. Die Leistungsfähigkeit dieses Ansatzes wird mit Hilfe von Simulationen realistischer Szenarien nachgewiesen. KW - Stadtverkehr KW - Verkehrsablauf KW - Netzwerkfluss KW - Optimierung KW - Netzwerkfluss KW - Verkehrsfluss KW - Konfluenter Fluss KW - Lichtsignalanlagenoptimierung KW - Optimierung von Wegweisern KW - Network flow KW - Traffic flow KW - Confluent flow KW - Traffic signal optimization KW - Flow with path restrictions Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus-23637 ER - TY - THES A1 - Reich, Alexander T1 - Cycle bases of graphs and spanning trees with many leaves - complexity results on planar and regular graphs T1 - Kreisbasen von Graphen und spannende Bäume mit vielen Blättern - Komplexitätsergebnisse zu planaren und regulären Graphen N2 - A cycle basis of a graph is a basis of its cycle space, the vector space which is spanned by the cycles of the graph. Practical applications for cycle bases are for example the optimization of periodic timetables, electrical engineering, and chemistry. Often, cycle bases belong to the input of algorithms concerning these fields. In these cases, the running time of the algorithm can depend on the size of the given cycle basis. In this thesis, we study the complexity of finding minimum cycle bases of several types on different graph classes. As a main result, we show that the problem of minimizing strictly fundamental cycle bases on planar graphs is NP-complete. We also give a similarly structured proof for problem of finding a maximum leaf spanning tree on the very restricted class of cubic planar graphs. Additionally, we show that this problem is APX-complete on k-regular graphs for odd k greater than 3. Furthermore, we classify types of robust cycle bases and study their relationship to fundamental cycle bases. N2 - Eine Kreisbasis eines Graphen ist eine Basis des Zyklenraumes des Graphen, also des Vektorraumes, der von den Kreisen des Graphen aufgespannt wird. Praktische Anwendungsgebiete von Kreisbasen finden sich zum Beispiel bei der Optimierung von Taktfahrplänen, in der Elektrotechnik und der Chemie. Oft gehören Kreisbasen zur Eingabe von Algorithmen aus diesen Gebieten. In diesen Fällen kann die Laufzeit der Algorithmen von der Größe der eingegebenen Kreisbasis abhängen. In dieser Arbeit untersuchen wir die Komplexität, minimale Kreisbasen unterschiedlicher Typen auf verschiedenen Graphenklassen zu finden. Als ein Hauptergebnis zeigen wir, dass das Problem minimale streng fundamentale Kreisbasen von planaren Graphen zu finden NP-vollständig ist. Wir geben einen ähnlich strukturierten Beweis für das Problem, auf der sehr eingeschränkten Graphenklasse der kubischen planaren Graphen einen spannenden Baum mit der maximalen Anzahl an Blättern zu finden. Zusätzlich zeigen wir, dass dieses Problem auf k-regulären Graphen für ungerade k größer als 3 APX-vollständig ist. Ein weiteres Thema der Arbeit ist die Klassifizierung von Typen robuster Kreisbasen und ihre Beziehung zu fundamentalen Kreisbasen. KW - Planarer Graph KW - Zyklenraum KW - NP-vollständiges Problem KW - Spannbäume mit vielen Blättern KW - Minimale streng fundamentale Kreisbasen KW - NP-Vollständigkeit KW - APX-Vollständigkeit KW - Planare Graphen KW - Maximum leaf spanning tree KW - Minimum strictly fundamental cycle basis KW - NP-completeness KW - APX-completeness KW - Planar graphs Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus-30692 ER -