Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
On bounding the difference of the maximum degree and clique number
No full textFor every k ∈ ℕ0, we consider graphs in which for any induced subgraph, Δ ≤ ω−1+k holds, where Δ is the maximum degree and ω is the maximum clique number of the subgraph. We give a finite forbidden induced subgraph characterization for every k. As an application, we find some results on the chromatic number χ of a graph. B.Reed stated the conjecture that for every graph, χ ≤ ⌈Δ+ω+1 / 2⌉ holds. Since this inequality is fulfilled by graphs in which Δ ≤ ω+2 holds, our results provide a hereditary graph class for which the conjecture holds
A practical mixed-integer programming model for the vertex separation number problem
No full textWe present a novel mixed-integer programming formulation for the vertex separation number problem in general directed graphs. The model is conceptually simple and, to the best of our knowledge, much more compact than existing ones. First experiments give hope that it can solve larger instances than has been possible so far if it is combined with preprocessing techniques to reduce the search space
Planar Octilinear Drawings with One Bend Per Edge
No full textIn octilinear drawings of planar graphs, every edge is drawn as a sequence of horizontal, vertical and diagonal (45°) line segments. In this paper, we study octilinear drawings of low edge complexity, i.e., with few bends per edge. A k-planar graph is a planar graph in which each vertex has degree at most k. In particular, we prove that every 4-planar graph admits a planar octilinear drawing with at most one bend per edge on an integer grid of size O(n2) ×O(n). For 5-planar graphs, we prove that one bend per edge still suffices in order to construct planar octilinear drawings, but in super-polynomial area. However, for 6-planar graphs we give a class of graphs whose planar octilinear drawings require at least two bends per edge for some edges
Algorithms for Incremental Planar Graph Drawing and Two-page Book Embeddings
Full text linkSubject of this work are two problems related to ordering the vertices of planar graphs. The first one is concerned with the properties of vertex-orderings that serve as a basis for incremental drawing algorithms. Such a drawing algorithm usually extends a drawing by adding the vertices step-by-step as provided by the ordering. In the field of graph drawing several orderings are in use for this purpose. Some of them, however, lack certain properties that are desirable or required for classic incremental drawing methods. We narrow down these properties, and introduce the bitonic st-ordering, an ordering which combines the features only available when using canonical orderings with the flexibility of st-orderings. The additional property of being bitonic enables an st-ordering to be used in algorithms that usually require a canonical ordering. With this in mind, we describe a linear-time algorithm that computes such an ordering for every biconnected planar graph. Unlike canonical orderings, st-orderings extend to directed graphs, in particular planar st-graphs. Being able to compute bitonic st-orderings for planar st-graphs is of particular interest for upward planar drawing algorithms, since traditional incremental algorithms for undirected planar graphs might be adapted to directed graphs. Based on this observation, we give a full characterization of the class of planar st-graphs that admit such an ordering. This includes a linear-time algorithm for recognition and ordering. Furthermore, we show that by splitting specific edges of an instance that is not part of this class, one is able to transform it into one for which then such an ordering exists. To do so, we describe a linear-time algorithm for finding the smallest set of edges to split. We show that for a planar st-graph G=(V,E), |V|−3 edge splits are sufficient and every edge is split at most once. This immediately translates to the number of bends required for upward planar poly-line drawings. More specifically, we show that every planar st-graph admits an upward planar poly-line drawing in quadratic area with at most |V|−3 bends in total and at most one bend per edge. Moreover, the drawing can be obtained in linear time. The second part is concerned with embedding planar graphs with maximum degree three and four into books. Besides providing a simplified incremental linear-time algorithm for embedding triconnected 3-planar graphs into a book of two pages, we describe a linear-time algorithm to compute a subhamiltonian cycle in a triconnected 4-planar graph
More General Optimal Offset Assignment
No full textThis manuscript presents exact approaches to the general offset assignment problem arising in the address code generation phase of compilers for application-specific processors. First, integer programming models for architecture-dependent and theoretically motivated special cases of the problem are established. Then, these models are extended to provide the first widely applicable formulations for the most general problem setting, supporting processors with several address registers and complex addressing capabilities. Existing heuristics are
similarly extended and practical applicability of the proposed methods is demonstrated by experimental evaluation using an established and large benchmark set. The experiments allow us to study the impact of exploiting more complex memory addressing capabilities on the address computation costs of real-world programs. We also show how to integrate operand reordering techniques for commutative instructions into existing solution approaches
Freight car dispatching with generalized flows
No full textIn the freight car dispatching problem empty freight cars have to be assigned to known demands respecting a given time horizon and certain constraints. The goal is to minimize the resulting transportation costs. One of the constraints is that customers can specify the type of cars they want. It is possible, however, that cars of certain types can be substituted by other cars, either in a 1-to-1 fashion or at different exchange rates. We show that these substitutions make the dispatching problem hard to solve and hard to approximate. We model the dispatching problem as an integral generalized transportation problem on a bipartite graph. Using rounding techniques, the LP-relaxation can be transformed to a transportation schedule violating some of the constraints slightly. Under an additional assumption on the cost function we fix this violation and derive a -approximation of the problem
An Integer Programming Approach to Optimal Basic Block Instruction Scheduling for Single-Issue Processors
No full textWe present a novel integer programming formulation for basic block instruction scheduling on single-issue processors. The problem can be considered as a very general sequential task scheduling problem with delayed precedence-constraints. Our model is based on the linear ordering problem and has, in contrast to the last IP model proposed, numbers of variables and constraints that are strongly polynomial in the instance size. Combined with improved preprocessing techniques and given a time limit of ten minutes of CPU and system time, our branch-and-cut implementation is capable to solve all but eleven of the 369,861 basic blocks of the SPEC 2000 integer and floating point benchmarks to proven optimality. This is competitive to the current state-of-the art constraint programming approach that has also been evaluated on this test suite
Exact Integer Programming Approaches to Sequential Instruction Scheduling and Offset Assignment
No full textThe dissertation at hand presents the main concepts and results derived when studying the optimal solution of two NP-hard compiler optimization problems, namely instruction scheduling and offset assignment, by means of integer programming. It is the outcome of several years of research as an assistant at Michael Jünger's computer science chair in Cologne, with the particular aim to apply exact mathematical optimization techniques to real-world problems arising in the domain of technical computer science. The two problems studied are rather unrelated apart from the fact that they both take place during the machine code generation phase of a compiler and deal with the handling of limited resources. Instruction scheduling is about the assignment of issue clock cycles to instructions in the presence of precedence, latency, and resource constraints such that the total time needed to execute all the instructions is minimized. Offset assignment deals with storage layouts of program variables and the efficient use of address registers for accesses to these variables. The objective is to employ specialized instructions in order to minimize the overhead caused by address computations. While instruction scheduling needs to be carried out by almost every present compiler irrespective of the processor architecture, the offset assignment problem occurs mainly in compilers for highly specialized processor designs. Instruction scheduling is a well-studied field where several exact and heuristic approaches have been developed and experimentally evaluated in the past. In this thesis, we concentrate on the basic-block instruction scheduling problem for single-issue processors. Basic blocks are program fragments with no side-entrances and -exits, i.e., every instruction of a basic block needs to be executed before the control flow may leave it and enter another basic block. Single-issue processors are capable of starting the execution of exactly one instruction per clock cycle. A number of techniques to preprocess instances of the basic-block instruction scheduling problem were proposed in the literature and are, with emphasis on the more recent ones that arose since the year 2000, thoroughly reviewed in this thesis. They finally led to a constraint programming approach in 2006 that was shown to solve about 350,000 instances to optimality and where some of these instances comprised up to about 2,500 instructions. The last attempt to tackle the problem using integer programming however dates to a time prior to the publication of the latest preprocessing advances. While being successful on a set of instances that impose very restrictive latency constraints, it was shown to be unable to solve hundreds of instances from the aforementioned benchmark set that comprises also large and varying latencies. In addition, the previous integer programming models were almost all based on so-called time-indexed formulations where decision variables model an explicit assignment of instructions to clock cycles. In this thesis, a completely different and novel approach is taken based on the linear ordering problem, a well-studied combinatorial optimization problem. The new models lead to alternative characterizations of the feasible solutions to the basic-block instruction scheduling problem. These facilitate the employment of advanced integer programming methodologies, in particular the design of branch-and-cut algorithms that can handle larger instances. The formulations are further extended by additional inequalities that can be used as cutting planes. Combined with the preprocessing routines that are partially extended and improved as well, the respective solver implementation eventually turned out to be competitive to the constraint programming method. Reaching this point has taken some years and this thesis presents not only the derived models but also several ideas and byproducts that arose in the meantime, and that can help and inspire researchers even if they aim at the application of different solution methodologies. The starting point regarding the offset assignment problem was a different one because especially exact solution approaches were rather rare prior to the models presented in this thesis. The offset assignment problem arose in the 1990s and is considered in several variants that are of theoretical and practical interest. In the simplest one, a processor is assumed to provide only a single address register and only very restricted possibilities to avoid address computation overhead. However, even this simplest variant, that may serve as a building block for the more complex ones, is already NP-hard and has been studied mainly from a heuristic point of view. The few existing exact solution approaches were not capable to solve moderately sized instances so that the quality of heuristic solutions relative to the optimum was hardly known at all. Again, the inspection of the combinatorial structure of the various problem variants turned out to be the key for designing branch-and-cut implementations that can profit from knowledge about related combinatorial optimization problems. The implementation targeting the simple problem variant was the first capable to optimally solve the majority of about 3,000 instances collected in a standard benchmark set. The method could then be further generalized in two steps. First, in a collaboration with Roberto Castañeda Lozano, additional techniques could be incorporated into the approach in order to handle multiple address registers. Fortunately, the methods could then even be further extended to as well deal with more flexible addressing capabilities. In this way, the thesis at hand does not only answer the question how large the address computation overhead can be when using heuristics, but as well presents first results that allow to analyze the impact of the mentioned increased addressing capabilities on the runtime performance and size of real-world programs
Modellbasierte Parallelisierung von Anwendungen zur Verkehrssimulation - Ein dynamischer und adaptiver Ansatz
No full textThe project Computer Aided Tram Scheduling (CATS) is concerned with the design and
implementation of methods and software tools that enable transport providers to generate,
simulate, and evaluate tram schedules on their own notebook or desktop computers.
The scientific interest lies in the research and development of the required concepts and
methods, these are mainly based in the areas of mathematical optimization and discrete
simulation. In this context originated the desire for a parallel simulation software, which
would be more accurate and also faster than the existing sequential model.
This thesis attends to three main goals:
At first a method for the parallel execution of discrete simulation models will be devised,
which should utilize properties of (amongst others) traffic simulation models. To
use the resources of the target platforms to the full extend, the approach should include
a dynamic and adaptive load balancing scheme. The method will be implemented as a
software framework, its dynamic behavior will be examined by conducting experiments
on example applications.
Furthermore, the software tools designed and implemented for project CATS will be
presented. The thesis concentrates on a simulation module based on the described framework,
which can be utilized to examine dynamic properties of tram schedules. To find
candidates for this, an optimization module should be applied which generates robust
tram schedules that also adhere to given sets of transport planning requirements.
At last, the presented software tools should be applied to the tram networks of the
cities of Cologne, Germany, and Montpellier, France. The optimizer should be applied to
generate both robust and non-robust schedules for these networks, which will be simulated,
evaluated, and compared to the schedules applied by the tram network providers.
The thesis begins with an introduction of context, motivation and aims (chapter 1),
followed by some background on methods of the parallel execution of discrete simulation
models (chapter 2). After this a method is proposed which is especially suitable for the
parallel execution of discrete traffic simulation models. The section begins by outlining
the ideas of the method and its realization, followed by some thoughts on its scalability
and efficiency (chapter 3). The thesis then continues by showing an implementation of the
method as a software framework for simulation applications (chapter 4), followed by the
description of some experiments conducted on a model of token movements on randomly
generated graphs, based on the presented framework (chapter 5). This is followed by an
application of method and framework in the simulation of tram schedules. Background
and architecture of project CATS are described, the applied simulation and optimization
models presented. These modules are utilized to generate and evaluate tram schedules
for the networks of the cities of Cologne and Montpellier. This is followed by some
observations on the run time behavior of the simulation module (chapter 6). The thesis
concludes with a short summary and some thoughts on further research (chapter 7)