Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
Modeling time table based tram traffic
No full textIn mid-sized cities, tram networks are a major component of the public service infrastructure. In those networks with their typically dense schedules multiple lines share tracks and stations, resulting in a dynamic system behavior and mounting delays following even small disruptions. Robustness is an important factor to keep delays from spreading through the network and to minimize average delays. As part of a project on simulation and optimization of robust schedules, this paper describes the development, implementation and application of a simulation model representing a tram network and its assigned time table. We begin by describing the components of a tram network, which consist of physical and logical entities. These concepts are then integrated into a model of time table based tram traffic. We apply the resulting simulation software to our hometown Cologne's tram network and present some experimental results
Via Minimization in VLSI Chip Design - Application of a Planar Max-Cut Algorithm
No full textThe design of very large scale integrated (VLSI) chips is an exciting area of applied discrete mathematics.Due to the intractability of the majority of the problems, and also due to the huge instance sizes, the design process is decomposed into various sub-problems. In this paper, for a given detailed routing solution, we revisit the assignment of layers to net segments. For connected metalized nets, a layer change is accomplished by a vertical interconnection area (via). We seek to minimize the use of these vias as vias not only reduce the electrical reliability and performance of the chip, but also decrease the manufacturing yield substantially. In the general case, the via minimization problem is NP-hard. However, it is known that the two layer via minimization problem can be solved as a maximum cut problem on a planar graph which is a polynomial task.The focus of this paper is to use this approach for modern real-world chips. From the roughly two dozen wiring layers present, we take two adjacent ones for the via minimization. As a core-routine, we use a fast maximum cut algorithm on planar graphs. For being able to use the solutions in practice, we integrate practically relevant design rule constraints at the expense of potentially using further vias. Thus, our solution satisfies the additional constraints present in actual current designs. The computational results show that our implementation is fast on real-world instances as it usually computes a solution within a few minutes CPU time only. Moreover, often a considerable amount of vias can be saved
On the existence of total dominating subgraphs with a prescribed additive hereditary property
No full textRecently, Bacsô and Tuza gave a full characterization of the graphs for which every connected induced subgraph has a connected dominating subgraph satisfying an arbitrary prescribed hereditary property. Using their result, we derive a similar characterization of the graphs for which any isolate-free induced subgraph has a total dominating subgraph that satisfies a prescribed additive hereditary property. In particular, we give a characterization for the case where the total dominating subgraphs are disjoint union of complete graphs. This yields a characterization of the graphs for which every isolate-free induced subgraph has a vertex-dominating induced matching, a so-called induced paired-dominating set
Efficient total domination in digraphs
No full textWe generalize the concept of efficient total domination from graphs to digraphs. An efficiently total dominating set X of a digraph D is a vertex subset such that every vertex of D has exactly one predecessor in X . Not every digraph has an efficiently total dominating set. We study graphs that permit an orientation having such a set and give complexity results and characterizations concerning this question. Furthermore, we study the computational complexity of the (weighted) efficient total domination problem for several digraph classes. In particular we deal with most of the common generalizations of tournaments, like locally semicomplete and arc-locally semicomplete digraphs
A Satisfiability-based Approach for Embedding Generalized Tanglegrams on Level Graphs
No full textA tanglegram is a pair of trees on the same set of leaves with matching leaves in the two trees joined by an edge. Tanglegrams are widely used in computational biology to compare evolutionary histories of species. In this paper we present a formulation of two related combinatorial embedding problems concerning tanglegrams in terms of CNF-formulas. The first problem is known as planar embedding and the second as crossing minimization problem. We show that our satisfiability formulation of these problems can handle a much more general case with more than two, not necessarily binary or complete, trees defined on arbitrary sets of leaves and allowed to vary their layouts
Reducing blocking effects in multi-block layouts
No full textTour planning in multi-block layouts is a common exercise in logistics. In those systems, blocking effects result from conflicting agents competing for resources. Although clearly exceptional in real world applications, most methods of tour planning assume only one active agent, and thus do not consider blocking effects. In this paper we examine heuristic methods of tour planning in multi-block layouts with multiple agents, finding that blocking effects have a significant impact on system performance. We show that methods devised for the mentioned special case do not scale very well when applied to scenarios with multiple agents. We propose a heuristic method which is capable of reducing blocking effects. It generates tours of equal or shorter length than those produced by the other examined methods
Towards shortest longest edges in orthogonal graph drawing
No full textInspired by a challenge during Graph Drawing 2010 "Find an orthogonal drawing whose longest edge is as short as possible", we investigate techniques to incorporate this goal into the "standard" topology-shape-metrics approach at moderate extra computational complexity.
Experiments indicate that this project is worth pursuing
Total domination versus paired domination
No full textA dominating set of a graph G is a vertex subset that any vertex of G either belongs to or is adjacent to. A total dominating set is a dominating set whose induced subgraph does not contain isolated vertices. The minimal size of a total dominating set, the total domination number, is denoted by gamma_t . The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Gamma_t . A paired dominating set is a dominating set whose induced subgraph has a perfect matching. The minimal size of a paired dominating set, the paired domination number, is denoted by gamma_p . The maximal size of an inclusionwise minimal paired dominating set, the upper paired domination number, is denoted by Gamma_p . In this paper we prove several results on the ratio of these four parameters: For each r ge 2 we prove the sharp bound gamma_p/gamma_t le 2 - 2/r for K_{1,r} -free graphs. As a consequence, we obtain the sharp bound gamma_p/gamma_t le 2 - 2/(Delta+1) , where Delta is the maximum degree. We also show for each r ge 2 that {C_5,T_r} -free graphs fulfill the sharp bound gamma_p/gamma_t le 2 - 2/r , where T_r is obtained from K_{1,r} by subdividing each edge exactly once. We show that all of these bounds also hold for the ratio Gamma_p / Gamma_t . Further, we prove that a graph hereditarily has an induced paired dominating set iff gamma_p le Gamma_t holds for any induced subgraph. We also give a finite forbidden subgraph characterization for this condition. We exactly determine the maximal value of the ratio gamma_p / Gamma_t taken over the induced subgraphs of a graph. As a consequence, we prove for each r ge 3 the sharp bound gamma_p/Gamma_t le 2 - 2/r for graphs that do not contain the corona of K_{1,r} as subgraph. In particular, we obtain the sharp bound gamma_p/Gamma_t le 2 - 2/Delta
Sentiment classification using statistical data compression
No full textWith growing availability and popularity of user generated content, the discipline of sentiment analysis has come to the attention of many researchers. Existing work has mainly focused on either knowledge-based methods or standard machine learning techniques. In this paper we investigate sentiment polarity classification based on adaptive statistical data compression models. We evaluate the classification precision of two lossless compression algorithms: the Lempel-Ziv-Welch-algorithm (LZW) and Prediction by Partial Matching (PPM). Comprehensive experiments on three different data sets show that with accuracies up to 95.68% the use of compression algorithms may be a promising alternative to standard sentiment analysis
An Exact Algorithm for Robust Network Design
No full textModern life heavily relies on communication networks that operate efficiently. A crucial issue for the design of communication networks is robustness with respect to traffic fluctuations, since they often lead to congestion and traffic bottlenecks. In this paper, we address an NP-hard single commodity robust network design problem, where the traffic demands change over time. For k different times of the day, we are given for each node the amount of single-commodity flow it wants to send or to receive. The task is to determine the minimum-cost edge capacities such that the flow can be routed integrally through the net at all times. We present an exact branch-and-cut algorithm, based on a decomposition into biconnected network components, a clever primal heuristic for generating feasible solutions from the linear-programming relaxation, and a general cutting-plane separation routine that is based on projection and lifting. By presenting extensive experimental results on realistic instances from the literature, we show that a suitable combination of these algorithmic components can solve most of these instances to optimality. Furthermore, cutting-plane separation considerably improves the algorithmic performance