Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
Partitioning planar graphs: a fast combinatorial approach for max-cut
No full textThe max-cut problem asks for partitioning the nodes V of a graph G=(V,E) into two sets (one of which might be empty), such that the sum of weights of edges joining nodes in different partitions is maximum. Whereas for general instances the max-cut problem is NP-hard, it is polynomially solvable for certain classes of graphs. For planar graphs, there exist several polynomial-time methods determining maximum cuts for arbitrary choice of edge weights. Typically, the problem is solved by computing a minimum-weight perfect matching in some associated graph. The most efficient known algorithms are those of Shih et al. and that of Berman et al. The running time of the former can be bounded by O(|V|^(3/2)log|V|). The latter algorithm is more generally for determining T-joins in graphs. Although it has a slightly larger bound on the running time of O([V|^(3/2)(log|V|)^(3/2))alpha(|V|), where alpha(|V|) is the inverse Ackermann function, it can solve large instances in practice. In this work, we present a new and simple algorithm for determining maximum cuts for arbitrary weighted planar graphs. Its running time is bounded by O(|V|^(3/2)log|V|), similar to the bound achieved by Shih et al. It can easily determine maximum cuts in huge random as well as real-world graphs with up to 10^6 nodes. We present experimental results for our method using two different matching implementations. We furthermore compare our approach with those of Shih et al. and Berman et al. It turns out that our algorithm is considerably faster in practice than the one by Shih et al. Moreover, it yields a much smaller associated graph. Its expanded graph size is comparable to that of Berman et al. However, whereas the procedure of generating the expanded graph in Berman et al. is very involved (thus needs a sophisticated implementation), implementing our approach is an easy and straightforward task
Generalized k-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation
No full textA tanglegram is a pair of (not necessarily binary) 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 work we present a
formulation of two related combinatorial embedding problems concerning tanglegrams in terms of CNF-formulas. The first problem is known as the planar embedding and the second as the crossing minimization problem. We show that our satisfiability-base encoding 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. Furthermore, we present an experimental comparison of our technique and several known heuristics for solving generalized binary tanglegrams, showing its competitive
performance and efficiency and thus proving its practical usability
Approximating Earliest Arrival Flows in Arbitrary Networks
No full textAbstract. The earliest arrival flow problem is motivated by evacuation planning. It asks for a flow over time in a network with supplies and demands that maximizes the satisfied demands at every point in time.
Gale [1959] has shown the existence of such flows for networks with a single source and sink. For multiple sources and a single sink the existence follows from work by Minieka [1973] and an exact algorithm has been
presented by Baumann and Skutella [FOCS ’06]. If multiple sinks are present, it is known that earliest arrival flows do not exist in general. We address the open question of approximating earliest arrival flows in arbitrary networks with multiple sinks and present constructive approx-
imations of time and value for them. We give tight bounds for the best possible approximation factor in most cases. In particular, we show that there is always a 2-value-approximation of earliest arrival flows and that
no better approximation factor is possible in general. Furthermore, we describe an FPTAS for computing the best possible approximation factor (which might be better than 2) along with the corresponding flow for any given instance
Improved Scalability By Using Hardware-Aware Thread Affinities
No full textThe complexity of an efficient thread management steadily rises with the number of processor cores and heterogeneities in the design of system architectures, e.g., the topologies of execution units and the memory architecture. In this paper, we show that using information about the system topology combined with a hardware-aware thread management is worthwhile. We present such a hardware-aware approach that utilizes thread affinity to automatically steer the mapping of threads to cores and experimentally analyze its performance. Our experiments show that we can achieve significantly better scalability and runtime stability compared to the ordinary dispatching of threads provided by the operating system
XSAT and NAE-SAT of linear CNF classes
No full textXSAT and NAE-SAT are important variants of the propositional
satisfiability problem (SAT). Both are studied here regarding their computational complexity of linear CNF formulas. We prove that
both variants remain NP-complete for (monotone) linear formulas
yielding the conclusion that also bicolorability of linear hypergraphs is NP-complete. The reduction used gives rise to the complexity investigation of both variants for several monotone linear subclasses that are parameterized by the size of clauses or by the number of
occurrences of variables. In particular cases of these parameter values we are able to verify the NP-completeness of XSAT
respectively NAE-SAT; though we cannot provide a complete treatment. Finally we focus on exact linear formulas where clauses intersect pairwise, and for which SAT is known to be polynomial-time solvable. We verify the same assertion for NAE-SAT relying on some well-known result; whereas we obtain NP-completeness for XSAT of exact linear formulas. The case of uniform clause size k remains open for the latter problem. However, we can provide its polynomial-time behavior for k at most 6
Global Approaches for Facility Layout and VLSI Floorplanning
No full textThis paper summarizes recent advances in the global solution of several relevant facility layout problems
Simulation ausgewählter Heuristiken zur Tourenplanung in manuellen Kommissionierstationen
No full textIm Folgenden werden die Auswirkungen des Einsatzes verschiedener Heuristiken zur Tourenplanung in manuellen Kommissionierstationen bei einem Pharmagroßhandel untersucht. Dabei wird nicht nur auf die Läange der Touren eingegangen, sondern zusätzlich die Auswirkung von Ressourcenkonflikten während der Kommissionierung auf die Dauer der Bedienzeiten betrachtet. Nach einer Beschreibung des Systems werden dazu zuerst der Entwurf und die Implementierung eines agentenbasierten Modells dargestellt. Daraufhin werden einige häufig verwendete Heuristiken eingeführt und für den Anwendungsfall evaluiert. Am Schluss steht eine kurze Zusammenfassung und ein Ausblick auf das weitere Vorgehen
Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges
No full textA set of planar graphs {G1(V,E1),…,Gk(V,Ek)} admits a simultaneous embedding if they can be drawn on the same pointset P of order n in the Euclidean plane such that each point in P corresponds one-to-one to a vertex in V and each edge in Ei does not cross any other edge in Ei (except at endpoints) for i∈{1,…,k}. A fixed edge is an edge (u,v) that is drawn using the same simple curve for each graph Gi whose edge set Ei contains the edge (u,v). We give a necessary and sufficient condition for two graphs whose union is homeomorphic to K5 or K3,3 to admit a simultaneous embedding with fixed edges (SEFE). This allows us to characterize the class of planar graphs that always have a SEFE with any other planar graph. We also characterize the class of biconnected outerplanar graphs that always have a SEFE with any other outerplanar graph. In both cases, we provide O(n4)-time algorithms to compute a SEFE
An SDP approach to multi-level crossing minimization
No full textWe present an approach based on semidefinite programs (SDP) to tackle the multi-level crossing minimization prob- lem. Thereby, we are given a layered graph (i.e., the graph´s vertices are assigned to multiple parallel levels) and ask for an ordering of the nodes on their levels such that, when draw- ing the graph with straight lines, the resulting number of crossings is minimized. Solving this step is crucial in the probably most widely used graph drawing scheme, the so- called Sugiyama framework. The problem has received a lot of attention both in the field of heuristics and exact methods. For a long time, integer linear programming (ILP) approaches were the only exact algorithms applicable at least to small graphs. Recently, SDP formulations for the special case of two levels were proposed and dominated the ILP for dense instances. In this paper, we present a new SDP formulation for the general multi-level version that, for two-levels, is even stronger than the aforementioned specialized SDP. As a side- product, we also obtain an SDP-based heuristic which in practice always gives (near-)optimal solutions. We conduct a large set of experiments, both on random- ized and on real-world instances, and compare our approach to a state-of-the-art ILP-based branch-and-cut implementa- tion. The SDP clearly dominates for denser graphs, while the ILP approach is usually faster for sparse instances. However, even for such sparse graphs, the SDP solves more instances to optimality than the ILP. In fact, there is no single instance the ILP solved, which the SDP did not. Overall, our experi- ments reveal that for sparse graphs, one should usually try to find an optimal solution with the ILP first. If this approach does not solve the instance to optimality within reasonable time, the SDP still has a good chance to do so. Being able to solve larger real-world instances than reported before, we are also able to evaluate heuristics for this problem. In this paper we do so for the traditional barycenter-heuristic (showing that it leaves a large gap to the true optimum) and the state-of-the-art upward-planarization method (showing that it is usually close to the optimum)
Paired and induced-paired domination in (E,net)-free graphs
No full textA dominating set of a graph is a vertex subset that any vertex belongs to or is adjacent to. Among the many well-studied variants of domination are the so-called paired-dominating sets. A paired-dominating set is a dominating set whose induced subgraph has a perfect matching. In this paper, we continue their study. We focus on graphs that do not contain the net-graph (obtained by attaching a pendant vertex to each vertex of the triangle) or the E-graph (obtained by attaching a pendant vertex to each vertex of the path on three vertices) as induced subgraphs. This graph class is a natural generalization of (claw,net)-free graphs, which are intensively studied with respect to their nice properties concerning domination and hamiltonicity. We show that any connected (E,net)-free graph has a paired-dominating set that, roughly, contains at most half of the vertices of the graph. This bound is a significant improvement to the known general bounds. Further, we show that any (E,net, C_5 )-free graph has an induced paired-dominating set, that is a paired-dominating set that forms an induced matching, and that such set can be chosen to be a minimum paired-dominating sets. We use these results to obtain a new characterization of (E,net, C_5 )-free graphs in terms of the hereditary existence of induced paired-dominating sets. Finally, we show that the induced matching formed by an induced paired-dominating set in a (E,net, C_5 )-free graph can be chosen to have at most two times the size of the smallest maximal induced matching possible