Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
Martin Grötschel’s Descendants and Their Doctoral Theses 1983–2012
No full textWe present the tree of Martin Grötschel’s doctoral descendants along with their doctoral theses from 1983 to 2012, i.e., the first 30 years. Our format should be self-explanatory: Depth in the hierarchy is indicated by indentation and color: blue for the 39 , red for the 74 , cyan for the 24 , and magenta for the 2 . The doctoral thesis titles of these 139 descendants show the many fruits of Martin Grötschel’s original impetus
Drawing Clustered Graphs as Topographic Maps
No full textThe visualization of clustered graphs is an essential tool for the analysis of networks, in particular, social networks, in which clustering techniques like community detection can reveal various structural properties.
In this paper, we show how clustered graphs can be drawn as topographic maps, a type of map easily understandable by users not familiar with information visu- alization. Elevation levels of connected entities correspond to the nested structure of the cluster hierarchy.
We present methods for initial node placement and describe a tree mapping based algorithm that produces an area efficient layout. Given this layout, a triangular ir- regular mesh is generated that is used to extract the elevation data for rendering the map. In addition, the mesh enables the routing of edges based on the topo- graphic features of the map
On the separability of graphs
No full textRecently, Cicalese and Milanič introduced a graph-theoretic concept called separability. A graph is said to be k-separable if any two non-adjacent vertices can be separated by the removal of at most k vertices. The separability of a graph G is the least k for which G is k-separable. In this paper, we investigate this concept under the following three aspects. First, we characterize the graphs for which in any non-complete connected induced subgraph the connectivity equals the separability, so-called separability-perfect graphs. We list the minimal forbidden induced
subgraphs of this condition and derive a complete description of the
separability-perfect graphs.We then turn our attention to graphs for which the separability is given locally by the maximum intersection of the neighborhoods of any two non-adjacent vertices. We prove that all (house,hole)-free graphs fulfill this property – a class properly including the chordal graphs and the distance-hereditary graphs. We conclude that the separability can be computed in O(m∆) time for such graphs.In the last part we introduce the concept of edge-separability, in analogy to edge-connectivity, and prove that the class of k-edge-separable graphs is closed under topological minors for any k. We explicitly give the forbidden topological minors of the k-edge-separable graphs for each 0 ≤ k ≤ 3
Sentiment classification using statistical data compression models
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 performance of the lossless compression algorithm Prediction by Partial Matching (PPM) as well as compression based measures using PPM-like character n-gram frequency statistics. Comprehensive experiments on three corpora show that compression based methods are efficient, easy to apply and can compete with the accuracy of sophisticated classifiers such as support vector machines
Agent-based modeling and simulation of individual traffic as an environment for bus schedule simulation
No full textTo re-establish the regular driving operations of a tram network, which was disturbed significantly by unforeseen external events, traffic schedulers apply rescheduling and rerouting strategies. These strategies are usually multi-modal; they consider the interaction of trams, buses, even taxis. Thus, to evaluate the applicability of a given rescheduling or rerouting strategy prior to its implementation in the real-world system, a multi-modal simulation software is needed. In this article we present an agent-based model of individual traffic which will be applied as background to a planned simulation of bus traffic. These combined models are to be integrated with an existing tram schedule simulation; the resulting multi-modal model will then be applied to evaluate the usefulness of given rescheduling or rerouting strategies. After a short introduction to agent-based modeling and simulation, as well as to existing models of individual traffic, this paper proposes to model the behavior of individual traffic as an environment for agent-based bus schedule simulation. Finally, some experiments are conducted by modeling and simulating individual traffic in Cologne's highly frequented Barbarossaplatz area
Lifting and Separation Procedures for the Cut Polytope
No full textThe max-cut problem and the associated cut polytope on complete graphs have been extensively studied over the last 25 years. However, little research has been conducted for the cut polytope on arbitrary graphs. In this study we describe new separation and lifting procedures for the cut polytope on such graphs. These procedures exploit algorithmic and structural results known for the cut polytope on complete graphs to generate valid, and sometimes facet defining, inequalities for the cut polytope on arbitrary graphs in a cutting plane framework. We report computational results on a set of well-established benchmark problems
Solving k-way Graph Partitioning Problems to Optimality: The Impact of Semidefinite Relaxations and the Bundle Method
No full textThis paper is concerned with computing global optimal solutions for maximum k-cut problems. We improve on the SBC algorithm of Ghaddar, Anjos and Liers in order to compute such solutions in less time. We extend the design principles
of the successful BiqMac solver for maximum 2-cut to the general maximum k-cut problem. As part of this extension, we investigate different ways of choosing variables for branching.We also study the impact of the separation of clique inequalities within this new framework and observe that it frequently reduces the number of subproblems considerably. Our computational results suggest that the proposed approach achieves a drastic speedup in comparison to SBC, especially when k = 3. We also made a comparison with the orbitopal fixing approach of Kaibel, Peinhardt and Pfetsch. The results suggest that while their performance is better for sparse instances and larger values of k, our proposed approach is superior for smaller k and for dense instances of medium size. Furthermore, we used CPLEX for solving the ILP formulation underlying the orbitopal fixing algorithm and conclude that especially on dense instances the new algorithm outperforms CPLEX by far
Facilitate SIMD-Code-Generation in the Polyhedral Model by Hardware-aware Automatic Code-Transformation
No full textAlthough Single Instruction Multiple Data (SIMD) units are available in general purpose processors already since the 1990s, state-of-the-art compilers are often still not capable to fully exploit them, i.e., they may miss to achieve the best possible performance.
We present a new hardware-aware and adaptive loop tiling approach that is based on polyhedral transformations and explicitly dedicated to improve on auto-vectorization. It is
an extension to the tiling algorithm implemented within the
PluTo framework. In its default setting, PluTo uses static tile sizes and is already capable to enable the use of SIMD units but not primarily targeted to optimize it. We experimented with different tile sizes and found a strong relationship between their choice, cache size parameters and
performance. Based on this, we designed an adaptive procedure that specifically tiles vectorizable loops with dynamically calculated sizes. The blocking is automatically fitted to the amount of data read in loop iterations, the available SIMD units and the cache sizes. The adaptive parts are built upon straightforward calculations that are experimentally verified and evaluated. Our results show significant improvements in the number of instructions vectorized, cache miss rates and, finally, running times
MolMap - Visualizing Molecule Libraries as Topographic Maps
No full textWe present a new application for graph drawing and visualization in the context of drug discovery. Combining the scaffold-based cluster hierarchy with molecular similarity graphs — both standard concepts in cheminfor- matics — allows one to get new insights for analyzing large molecule libraries. The derived clustered graphs represent different aspects of structural similarity. We suggest visualizing them as topographic maps. Since the cluster hierarchy does not reflect the underlying graph structure as in (Gronemann and Jünger, 2012), we suggest a new partitioning algorithm that takes the edges of the graph into account. Experiments show that the new algorithm leads to significant improvements in terms of the edge lengths in the obtained drawings
The Landscape Metaphor for Visualization of Molecular Similarities
No full textClustered graphs are a versatile representation formalism for expressing relations between entities, and simultaneously, reflecting their hierarchical structure. This makes clustered graphs well-suited to model complex structured data. However, obtaining appealing drawings of clus- tered graphs is a challenging task. We employ the landscape metaphor to visualize clustered graphs in a cheminformatics application. In order to browse chemical compound libraries in a systematic way, we consider two different molecular similarity concepts. Combining the scaffold-based cluster hierarchy with molecular similarity graphs allows for new insights in the analysis of large molecule libraries. Here, like in certain other application domains, the cluster hierarchy does not necessarily reflect the underlying graph structure. We improve the approach taken in [9] by ap- plying a modified treemap algorithm for node positioning that takes the edges of the graph into account. Experiments with real-world instances clearly show that the new algorithm leads to significant improvements in terms of the edge lengths