Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
Note on the number of rooted complete N-ary trees
No full textWe determine a recursive formula for the number of rooted complete N-ary trees with n leaves which generalizes the formula for the sequence of Wedderburn-Etherington numbers. The diagonal sequence of our new sequences equals to the sequence of numbers of rooted trees with N+1 vertices
Distance-hereditary digraphs
No full textExtending notions from undirected graphs, we introduce directed graphs with the property that distances are preserved when taking induced subdigraphs. We characterize these distance-hereditary digraphs in terms of paths, their level structure and forbidden induced subdigraphs. Weaker requirements than the preservation of distances allow the distance to increase by a multiplicative or additive constant. For these (k,{+,*})-distance-hereditary digraphs we give characterizations and provide computational complexity results for the corresponding recognition problems
Simulation zur Verbesserung der Logistikprozesse eines Pharmagroßhandels
No full textGehe Pharma Handel GmbH is one of Germany's biggest pharmaceutical wholesalers. This paper describes the development and application of a simulation software representing their logistic processes, built in cooperation with Gehe's Troisdorf branch. We start with an outline of the Gehe facility, describe the process of implementing and validating the software application, and show some sample results
10 Jahre FAI Projekt
No full textVor zehn Jahren wurde Version 1.0 der Software FAI (Fully Automatic Installation) veröffentlicht. Damals war FAI eine automatisierte Installationsprozedur für ein Cluster. Heute ist FAI ein universelles Werkzeug, das neben Installation und Softwareverteilung auch das Konfigurationsmanagement für verschiedene Linux Distributionen umfasst. Dabei wird die gesamte Computerinfrastruktur betrachtet und nicht einzelne Rechner, die es zu administrieren gilt. Im Laufe der letzten zehn Jahre hat sich das Tool stetig weiterentwickelt und ist heute als wichtiges Werkzeug für Administratoren etabliert
A Generalized Flow Network for Freight Car Dispatching
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 NP-complete. We model the dispatching problem as a generalized integral minimum cost flow problem on a specific directed graph. We show that in our setting its linear relaxation is half-integral. Using rounding techniques, the LP-relaxation can be transformed to a dispatching with small constraint violation at the same cost, or, under additional assumptions, to a 4 -approximation. In practice, both ideas are combined to a heuristic approach without further assumptions. We conclude with computational results for this heuristic on application data provided by DB Schenker Rail Deutschland AG in context of a joint R-and-D project together with the Technical University of Kaiserslautern
Exact Bipartite Crossing Minimization under Tree Constraints
No full textA tanglegram consists of a pair of (not necessarily binary) trees T_1, T_2 with leaf sets L_1, L_2. Additional edges, called tangles, may connect nodes in L_1 with those in L_2. The task is to draw the tanglegram with a minimum number of tangle edge crossings while making sure that no crossing occurs between edges within each tree. This problem has relevant applications in computational biology, e.g., for the comparison of phylogenetic trees. In this work, we show that the problem can be formulated as a quadratic linear ordering problem (QLO) with additional side constraints. It was already shown that, appropriately reformulated, the QLO polytope is a face of some cut polytope. It turns out that the additional side constraints arising in our application do not destroy this property. Therefore, any polyhedral approach to max-cut can be used in our context. We present experimental results for drawing random and realistic tanglegrams using both linear and semidefinite programming techniques, showing that our approach is very efficient in practice
A Non-Disordered Glassy Model with a Tunable Interaction Range
No full textWe introduce a non-disordered lattice spin model, based on the principle of minimizing spin-spin correlations up to a (tunable) distance R.The model can be defined in any spatial dimension D, but already for D=1 and small values of R (e.g. R=5) the model shows the properties of a glassy system: deep and well separated energy minima, very slow relaxation dynamics, aging and non-trivial fluctuation-dissipation ratio
The complexity of connected domination and total domination by restricted induced graphs
No full textGiven a graph class C, it is natural to ask whether a given graph has a connected or a total dominating set inducing a graph of C and, if so, what is the minimal size of such a set. We give a sufficient condition on C for the intractability of this problem. This condition is fulfilled by a wide range of graph classes
On the Use of Network Flow Techniques for Assigning Evacuees to Exits
No full textWe apply network flow techniques to find good exit selections for evacuees in an emergency evacuation. More precisely, we present two algorithms for computing exit distributions using both classical flows and flows over time which are well known from combinatorial optimization. The performance of these new proposals is compared to a simple shortest path approach and to a best response dynamics approach by using a cellular automaton model