Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
A Simulation Suite for Lattice-Boltzmann based Real-Time CFD Applications Exploiting Multi-Level Parallelism on Modern Multi- and Many-Core Architectures
No full textWe present a software approach to hardware-oriented numerics which builds upon an augmented, previously published open-source set of libraries facilitating portable code development and optimisation on a wide range of modern computer architectures. In order to maximise eficiency, we exploit all levels of arallelism, including vectorisation within CPU cores, the Cell BE and GPUs, shared memory thread-level parallelism between cores, and parallelism between heterogeneous distributed memory resources in clusters. To evaluate and validate our approach, we implement a collection of modular building blocks for the easy and fast assembly and development of CFD applications based on the shallow water equations: We combine the Lattice-Boltzmann method with i-uid-structure interaction techniques in order to achieve real-time simulations targeting interactive virtual environments. Our results demonstrate that recent multi-core CPUs outperform the Cell BE, while GPUs are significantly faster than conventional multi-threaded SSE code. In addition, we verify good scalability properties of our application on small clusters
Basic Introduction to Algorithms and Data Structures
No full textThis chapter was written for the International Summer School "Modern Computational Sciences" 2011. It gives a brief introduction into basic data structures and algorithms, together with references to tutorials available in the literature. We first introduce fundamental notation and algorithmic concepts. We then explain several sorting algorithms and give small examples. As fundamental data structures, we introduce linked lists, trees and graphs. Implementations are given in the programming language C
When the connected domination number is at most the total domination number
No full textIn this note we give a finite forbidden subgraph characterization of the connected graphs for which any non-trivial connected induced subgraph has the property that the connected domination number is at most the total domination number. This question is motivated by the fact that any connected dominating set of size at least 2 is in particular a total dominating set. It turns out that in this characterization, the total domination number can equivalently be substituted by the upper total domination number, the paired-domination number and the upper paired-domination number respectively. Another equivalent condition is given in terms of structural domination
On separation pairs and split components of biconnected graphs
No full textThe decomposition of a biconnected graph G into its triconnected components is fundamental in graph theory and has a wide range of applications. Based on a palm tree of G, the algorithm by Hopcroft and Tarjan is able to compute them in linear time if some corrections are applied.
Today, the algorithm is still considered very hard to understand and proofs of its correctness are technical and challenging.
The article at hand provides a more comprehensive description of the algorithm, making it easier to understand and implement. Its correctness is validated by explicitly mapping the algorithmic detection criteria to
the graph-theoretic characterization of type-1 and type-2 separation pairs.
Further, it reveals further errors and inaccuracies in the common definitions. This includes the description and proofs of further properties and relationships of separation pairs. The presented results also answer the question whether and under which preconditions type-1 and type-2 pairs can be computed separately from each other
Dynamic Distributed Simulation of DEVS Models on the OSGi Service Platform
Get PDFInteroperability among simulators is one of the key factors in distributed simulations. Several interoperability infrastructures such as HLA and DEVS/SOA have been utilised, but most of them do not provide any dynamics. This paper introduces the use of the OSGi service platform as universal middleware for dynamic distributed simulation of DEVS models. We have designed and implemented the DEVS/OSGi simulation framework, which is an approach similar to DEVS/SOA, but relies on an integrated service-oriented and protocol independent architecture. It enables standardized plug-and-play capabilities and dynamic reconfiguration within distributed simulations. The architecture and implementation has been validated in an analytical context against a traffic simulation model. We conclude that the standardised interoperability and run-time dynamics provided by the OSGi service platform are highly valuable for distributed simulations
Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-Cut
No full textWe consider the Steiner tree problem under a two-stage stochastic model with recourse and finitely many scenarios. In this prob- lem, edges are purchased in the first stage when only probabilistic infor- mation on the set of terminals and the future edge costs is known. In the second stage, one of the given scenarios is realized and additional edges are puchased in order to interconnect the set of (now known) ter- minals. The goal is to decide on the set of edges to be purchased in the first stage while minimizing the overall expected cost of the solution. We provide a new semi-directed cut-set based integer programming formula- tion, which is stronger than the previously known undirected model. We suggest a two-stage branch-and-cut (B&C) approach in which L-shaped and integer-L-shaped cuts are generated. In our computational study we compare the performance of two variants of our algorithm with that of a B&C algorithm for the extensive form of the deterministic equiva- lent (EF). We show that, as the number of scenarios increases, the new approach significantly outperforms the (EF) approach
Simplifying Maximum Flow Computations: the Effect of Shrinking and Good Initial Flows
No full textMaximum-flow problems occur in a wide range of applications. Although already well-studied, they are still an area of active research. The fastest available implementations for determining maximum flows in graphs are either based on augmenting-path or on push-relabel algorithms. In this work, we present two ingredients that, appropriately used, can considerably speed up these methods. On the theoretical side, we present flow-conserving conditions under which subgraphs can be contracted to a single vertex. These rules are in the same spirit as presented by Padberg and Rinaldi (Math. Programming (47), 1990) for the minimum cut problem in graphs. These rules allow the reduction of known worst-case instances for different maximum flow algorithms to equivalent trivial instances. On the practical side, we propose a two-step max-flow algorithm for solving the problem on instances coming from physics and computer vision. In the two-step algorithm flow is first sent along augmenting paths of restricted lengths only. Starting from this flow, the problem is then solved to optimality using some known max-flow methods. By extensive experiments on instances coming from applications in theoretical physics and in computer vision, we show that a suitable combination of the proposed techniques speeds up traditionally used methods
A note on connected dominating sets of distance-hereditary graphs
No full textA vertex subset of a graph is a dominating set if every vertex of the graph belongs to the set or has a neighbor in it. A connected dominating set is a dominating set such that the induced subgraph of the set is a connected graph. A graph is called distance-hereditary if every induced path is a shortest path. In this note, we give a complete description of the (inclusionwise) minimal connected dominating sets of connected distance-hereditary graphs in the following sense: If G is a connected distance-hereditary graph that has a dominating vertex, any minimal connected dominating set is a single vertex or a pair of two adjacent vertices. If G does not have a dominating vertex, the subgraphs induced by any two minimal connected dominating sets are isomorphic. In particular, any inclusionwise minimal connected dominating set of a connected distance-hereditary graph without dominating vertex has minimal size. In other words, connected distance-hereditary graphs without dominating vertex are connected well-dominated. Furthermore, we show that if G is a distance-hereditary graph that has a minimal connected dominating set X of size at least 2, then for any connected induced subgraph H it holds that the subgraph induced by any minimal connected dominating set of H is isomorphic to an induced subgraph of G[X]
Agent based modeling and simulation of a pastoral-nomadic land use system
No full textAlmost half of Africa is covered by arid savannas, which are used as rangelands and are the source of livelihood for a vast population. To sustain pasture quality, degradation has to be avoided and efficient and sustainable land use strategies are needed. This paper describes the development of a simulation model representing the range management strategies of the Himba people in north-western Namibia. The model recognizes spatial factors and the impact of management decisions on ecosystem dynamics. The paper also describes the process of creating and validating a software application, and implementing the model
Speeding up IP-based Algorithms for Constrained Quadratic 0-1 Optimization
No full textIn many practical applications, the task is to optimize a non-linear objective function over the vertices of a well-studied polytope as, e.g., the matching polytope or the travelling salesman polytope (TSP).Prominent examples are the quadratic assignment problem and the quadratic knapsack problem; further applications occur in various areas such as production planning or automatic graph drawing. In order to apply branch-and-cut methods for the exact solution of such problems, the objective function has to be linearized. However, the standard linearization usually leads to very weak relaxations. On the other hand, problem-specific polyhedral studies are often time-consuming.Our goal is the design of general separation routines that can replace detailed polyhedral studies of the resulting polytope and that can be used as a black box. As unconstrained binary quadratic optimization is equivalent to the maximum cut problem, knowledge about cut polytopes can be used in our setting. Other separation routines are inspired by the local cuts that have been developed by Applegate, Bixby, Chvatal and Cook for faster solution of large-scale traveling salesman instances. Finally, we apply quadratic reformulations of the linear constraints as proposed by Helmberg, Rendl and Weismantel for the quadratic knapsack problem. By extensive experiments, we show that a suitable combination of these methods leads to a drastical speedup in the solution of constrained quadratic 0-1 problems. We also discuss possible generalizations of these methods to arbitrary non-linear objective functions