Refine
Document Type
- Doctoral thesis (5)
Has Fulltext
- yes (5)
Is part of the Bibliography
- no (5)
Language
- English (5) (remove)
Keywords
- Graphensuche (2)
- APX-Hardness (1)
- APX-Vollständigkeit (1)
- APX-completeness (1)
- Asteroidal triples (1)
- Asteroidale Tripel (1)
- Binary methods (1)
- Confluent flow (1)
- Convex geometry (1)
- Dynamic algorithm (1)
Institute
- FG Diskrete Mathematik und Grundlagen der Informatik (5) (remove)
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.
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.
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.
Signalized flows - optimizing traffic signals and guideposts and related network flow problems
(2011)
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.
Color sequencing
(2004)
In this dissertation, we present several solution approaches for the color change minimization problem that arises in the paint shop of an automobile plant. We give NP-completeness results for an abstract formulation of this problem and show that it is APX-hard, even in a restricted form. For this form, we establish a connection to binary matroids. When solving the color change minimization problem with the help of a line storage system, we present dynamic programs that use algorithms from computational biology, among others. Finally, we look into the color change minimization problem within the overall production process of an automobile plant. We describe an algorithm that sequences a daily production and that has been successfully developed with and implemented in the Ford Motor Company (Europe).