Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
Single-Commodity Robust Network Design with Finite and Hose Demand Sets
No full textWe study a single-commodity Robust Network Design problem (sRND) defined on an undirected graph. Our goal is to determine minimum cost capacities such that any traffic demand from a given uncertainty set can be satisfied by a feasible single-commodity flow. We consider two ways of representing the uncertainty set, either as a finite list of scenarios or as a polytope. We propose a branch-and-
cut algorithm to derive optimal solutions to sRND, built on a capacity-based integer linear programming formulation. It is strenghtened with valid inequalities derived as {0,1/2 }-Chvátal-Gomory cuts. Since the formulation contains exponentially many constraints, we provide practical separation algorithms. Extensive computational experiments show that our approach is effective, in comparison to existing approaches from the literature as well as to solving a flow based formulation by a general purpose solver
Two-Page Book Embeddings of 4-Planar Graphs (Extended Draft Version)
No full textBack in the Eighties, Heath showed that every 3-planar graph is subhamiltonian and asked whether this result can be extended to a class of graphs of degree greater than three. In this paper we affirmatively answer this question for the class of 4-planar graphs. Our contribution consists of two algorithms: The first one is limited to triconnected graphs, but runs in linear time and uses existing methods for computing hamiltonian cycles in planar graphs. The second one, which solves the general case of the problem, is a quadratic-time algorithm based on the book-embedding viewpoint of the problem
Bitonic st-orderings of biconnected planar graphs
No full textVertex orderings play an important role in the design of graph drawing algorithms.
Compared to canonical orderings, st-orderings lack a certain property that is required by many drawing methods.
In this paper, we propose a new type of st-ordering for biconnected planar graphs that relates the ordering to the embedding.
We describe a linear-time algorithm to obtain such an ordering and demonstrate its capabilities with two applications
A robust schedule for Montpellier's Tramway network
No full textThe city of Montpellier in the Languedoc-Roussillon region of France features a fast growing tram network as a central part of its public service infrastructure. Here, as in many other tram networks, resources like tracks and stations are shared between different lines. Because of the resulting dependencies, small inevitable delays can spread through the network and affect its global performance.
Abstract This article examines whether a robust tram schedule may help to raise punctuality in Montpellier's tram network. To accomplish this, we apply a tool set designed to generate schedules optimized for robustness, which also satisfy given sets of planning requirements. These tools allow to compare time tables with respect to their punctuality and other key indicators.
Abstract After an introduction to the goals of this paper, we continue with a description of the tool set focusing on optimization and simulation modules. These software utilities are then employed to generate and simulate robust and non-robust schedules for Montpellier's tram network, which are subsequently compared for the resulting delays
Planar Octilinear Drawings with One Bend Per Edge (Extended Draft Version)
No full textIn octilinear drawings of planar graphs, every edge is drawn as an alternating 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 less or equal to 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(n^2)×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
Model-based parallelization of discrete traffic simulation models
No full textTo re-establish regular operations in a tram traffic network after a large disturbance, e.g. resulting from vehicle
breakdown or station closure, the viability of several rescheduling and rerouting strategies has to be evaluated
prior to their implementation. Here, a multi-modal traffic simulation system can help to enhance the
decision quality. Such a system obviously faces tight time constraints, so simulation data has to be acquired
fast.
In this paper we propose a method for the parallel execution of discrete traffic simulation models, which
would accelerate data generation in comparison to a sequential model. To assess this method's dynamic behavior
in real-world applications, some experiments conducted on a software system modeling schedule
based tram traffic are presented.
After giving an introduction to the scope and aim, we show some background on the parallelization of discrete
simulation models. The main part of the paper begins with the proposal of a method to parallelize the
execution of simulation models with problem specific properties. Some estimations of the method's efficiency
are shared, followed by several experiments to highlight its dynamic behavior in real-world applications.
The paper ends with a short summary and some thoughts on further research
More General Optimal Offset Assignment
No full textWe present 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-scale benchmark set. The experiments also allow us to study the impact of exploiting more complex memory addressing capabilities on the address computation costs of real-world programs. Further, we show how to integrate operand reordering techniques based on commutative instructions into existing solution approaches
Multi-depot multi-vehicle-type vehicle scheduling for Cologne’s tram network
No full textTo be a feasible base for simulation studies of Cologne's tram network, a valid vehicle schedule has to con-sider several requirements, like multiple vehicle depots and multiple types of vehicles. The local transport provider utilizes both low-floor and high-floor vehicles, with high-floor vehicles being qualified to serve both high-floor and low-floor platforms. Therefore mixed vehicle rotations are acceptable, but generally not desired. This paper presents a set of models which adhere to these requirements, while also considering sev-eral possible optimization goals, like minimum number of deployed vehicles, and minimum combined length of maintenance trips
Planar Octilinear Drawings with One Bend Per Edge
No full textIn octilinear drawings of planar graphs, every edge is drawn as an alternating 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 less or equal to 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(n^2)×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