Datum: Fr, 21 Jun 2013, 14:00

Ort: SR 301

Vortragende(r): Lukas Barth

Inhalt: Wir beschäftigen uns mit dem Problem, Word Clouds, wie sie zum Beispiel von der Website Wordle.net erzeugt werden, mit semantischen Informationen anzureichern. Hierfür wird ein Graph-basiertes Modell eingeführt. Für verschiedene Varianten dieses Problems wird NP-Schwere gezeigt, während für andere, sehr eingeschränkte Varianten Algorithmen mit polynomieller Zeitkomplexität vorgestellt werden. Für die Fälle, in denen das Problem NP-schwer ist, werden Approximationsalgorithmen vorgestellt. Abschließend werden diese Approximationsalgorithmen sowie eine frühere Heuristik experimentell evaluiert und verglichen.

Datum: Fr, 24 Mai 2013, 14:00

Ort: SR 301

Vortragende(r): Jan Christoph Athenstädt, Diplomarbeit

Inhalt: While there are a number of approaches for the visualization of clusterings in general, there exist only few attempts to visualize two different clusterings in the same drawing. In this thesis, we lay the theoretical foundations for the simultaneous visualization of two or more clusterings. We establish a class-hierarchy that allows us to characterize families of clusterings depending on their embeddability in the plane and show how the classes relate to known combinatorial problems. For some of these classes we can show the NP-completeness of deciding whether an instance belongs to the class. In these cases, we provide a simple heuristic that allows us to find a good, yet not optimal solution. We finally conducted some experiments regarding the quality of the heuristic and applied it of real-world data.

Datum: Fr, 24 Mai 2013, 11:30

Ort: SR 348

Vortragende(r): Uwe Korn, Bachelor-Arbeit

Inhalt: In the past, clustering techniques have focused on vector or graph data. However, today’s applications demand the combination of both. Although few techniques have been proposed to solve this, they are neither parameter-free nor outlier-aware. Furthermore, some of them, focused on attribute selection, are not applicable for large graphs as they are inefficient. In this thesis, we propose a novel measure for rating the quality of the clustering on attributed graphs. Regarding outlier detection, we use our clustering results to rank nodes w.r.t. their deviation from their assigned and neighbouring clusters. For the optimisation of the quality function, we present an algorithm scaffold which is instantiated with different approaches. Finally, the proposed approach has been evaluated on both synthetic and real world data. Results show that it is more effective and efficient than state-of-the-art approaches for outlier detection.

Datum: Fr, 17 Mai 2013, 14:00

Ort: SR 236

Vortragende(r): Julian Arz, Studienarbeit, SEA Papier

Inhalt: Transit Node Routing (TNR) is a fast and exact distance oracle for road networks. We show several new results for TNR. First, we give a surprisingly simple implementation fully based on contraction hierarchies that speeds up preprocessing by an order of magnitude approaching the time for just finding a contraction hierarchy (which alone has two orders of magnitude larger query time). We also develop a very effective purely graph theoretical locality filter without any compromise in query times.

Datum: Mi, 15 Mai 2013, 11:30

Ort: SR 236

Vortragende(r): Sebastian Meßmer, BA

Inhalt: Induced sorting is one of the modern ideas to construct suffix arrays efficiently. The basic algorithm sais was published by Nong et al. in [NZC09]. There is a fast, optimized implementation written by Yuta Mori which is called sais-lite [Mor10]. This implementation was extended to salcpis, which also constructs the LCP array on the fly by Johannes Fischer [Fis11]. In this thesis, we describe the optimizations, Yuta Mori implemented in sais-lite. We introduce some micro optimizations to sais-lite and to Fischer’s algorithm and evaluate the runtimes. We compare and evaluate different approaches that are denoted in [Fis11]. For example, we evaluate a recursive versus a non-recursive implementation and we test whether we can achieve a speedup by storing the suffix and LCP array interleaved. Taking the salcpis idea, we create lcpis, a pure LCP construction algorithm. This algorithm is then compared to state of the art LCP construction algorithms.

Datum: Fr, 3 Mai 2013, 14:00

Ort: SR 301

Vortragende(r): Philipp Loewner, BA

Inhalt: Wir zeigen, wie man den k-Core eines Graphen berechnet. Danach stellen wir die Reduktion von Rutter et al. von Dominating Set auf Subset k-CoreAugmentation vor und argumentieren, warum sie nicht ausreicht, um die NP-Vollständigkeit von Single Vertex k-CoreAugmentation zu zeigen. Basierend auf dieser Reduktion entwickeln wir eine neue und beweisen mit ihrer Hilfe, dass Single Vertex k-CoreAugmentation für variables k NP-vollständig ist. Anschließend zeigen wir, dass es Familien von Instanzen gibt, die mit einer Gütegarantie approximieren lassen, die nur von k - und damit nicht von der Größe des Eingabegraphen - abhängt.

Datum: Mi, 24 Apr 2013, 11:30

Ort: SR 236

Vortragende(r): Harris Kaufmann, Bachelor-Talk

Inhalt: Road networks with time-dependent edge weights can describe rush hours and similar regular changes in traffic over a day. Optimal routes can be calculated efficiently using time-dependent Contraction Hierarchies. On mobile devices it is usually not possible and also not reasonable to hold the entire data in the limited main memory. Therefore the main performance bottleneck is the data access on the flash memory, which can only be read blockwise. For fast route query calculations, the number of accessed blocks has to be low. To achieve this, we first reduce the amount of data using a lossy compression. This introduces inaccuracies in the calculations hence not always the optimal route is chosen. Nevertheless using this method the result is still nearly exact because the average introduced delay compared to the optimal route is less than 0.001%. In the worst case a delay of about 0.1% occurs which still is too small to be noticed. Second, the data is rearranged in a way that increases the locality. This leads to a lower number of required block loads. For a road network of Germany we can answer random route queries with an average of 102 block loads. Assuming that a block access takes 1.3 ms, this can be done in 133 ms. Users perceive this as a nearly instant reaction. Everyday route calculations tend to be even smaller and can be calculated faster.

Datum: Di, 19 Mär 2013, 14:00

Ort: SR 301

Vortragende(r): Robert Jungblut, Diplomarbeitsvortrag

Inhalt: Wir stellen das Problem np-flex vor: Gegeben seien die Planarisierung eines nichtplanaren Graphen mit Maximalgrad 4 sowie eine Abbildung flex, die jeder Kante des Graphen eine Flexibilität zuweist. Gibt es eine Orthogonale Zeichnung dieser planaren Einbettung, so dass jede Kante e höchstens flex(e) Knicke aufweist? Während dieses Problem für den planaren Fall wohl untersucht ist, ebenso wie für den Fall dass die Einbettung des Graphen frei gewählt werden darf, stellt dies die erste Arbeit dar, bei der feste Einbettungen nichtplanarer Graphen betrachtet werden.

Datum: Mi, 20 Feb 2013, 11:30

Ort: SR 236

Vortragende(r): Raoul Steffen, Diplomarbeitsvortrag

Inhalt: I present an algorithm for matrix inversion that combines the practical requirement of an optimal number of arithmetic operations and the theoretical goal of a polylogarithmic critical path length. The algorithm reduces inversion to matrix multiplication. It uses Strassen's recursion scheme but on the critical path, it breaks the recursion early switching to an asymptotically inefficient yet fast use of Newton's method. In experiments, I show that the algorithm outperfoms the routines from Intel's library MKL even on the moderate parallelism of multicore systems.

Datum: Di, 29 Jan 2013, 09:45

Ort: SR 301

Vortragende(r): Prof. Therese Biedl, University of Waterloo

Inhalt: In this lecture, we explore connections between the height of planar graph drawings and the so-called pathwidth. In particular, we show that any graph that has a planar drawing of height h also has pathwidth at most h. Then we explore which planar graphs can be drawn with height O(pathwidth) and obtain a positive answer for trees and outer-planar graphs, but a negative one for 2-outer-planar graphs and series-parallel graphs. Time permitting, we will also briefly discuss how using the pathwidth one can test in polynomial time (for a given constant h) whether a graph has a drawing of height h.

Datum: Fr, 25 Jan 2013, 14:30

Ort: SR 301

Vortragende(r): Johannes Fischer

Datum: Fr, 25 Jan 2013, 14:00

Ort: SR 301

Vortragende(r): Denis Knöpfle, Bachelorarbeiter

Inhalt: Die Arbeit beschreibt eine Anpassung von Sample Sort auf das Sortieren von Zeichenketten. Der Algorithmus wurde in C++ implementiert und mithilfe von OpenMP parallelisiert. Ergebnisse von Experimenten zeigen, dass der Algorithmus für sehr große Datensätze und vor allem für im Schnitt sehr lange Zeichenketten geeignet und effizient ist.

Datum: Mi, 16 Jan 2013, 12:00

Ort: SR 236

Vortragende(r): Jochen Speck

Inhalt: We give an efficient algorithm for solving the following scheduling problem to optimality: Assign n jobs to m processors such that they all meet a common deadline T and energy consumption is minimized by appropriately controlling the clock frequencies of the processors. Jobs are malleable, i.e., their amount of parallelism can be flexibly adapted. In contrast to previous work on energy efficient scheduling we allow more realistic energy consumption functions including a minimum and maximum clock frequency and a linear term in energy consumption. We need certain assumptions on the speedup function of the jobs that we show to apply for a large class of practically occurring functions.

Datum: Di, 18 Dez 2012, 14:00

Ort: SR 301

Vortragende(r): Marcel Radermacher

Inhalt: Die Arbeit präsentiert die erste effiziente Implementierung des Penalty-Verfahrens zur Berechnung von Alternativgraphen. Durch geschickte Ausnutzung von Multi-Level-Separatoren gelingt es Beschleunigungen von über eine Größenordnung gegenüber einer optimierten Version auf Basis des Algorithmus von Dijkstra zu erreichen.

Datum: Fr, 14 Dez 2012, 14:30

Ort: SR 301

Vortragende(r): Timo Bingmann

Inhalt: We consider text index construction in external memory (EM). Our first contribution is an inducing algorithm for suffix arrays in external memory. Practical tests show that this outperforms the previous best EM suffix sorter [Dementiev et al., ALENEX 2005] by a factor of about two in time and I/O-volume. Our second contribution is to augment the first algorithm to also construct the array of longest common prefixes (LCPs). This yields the first EM construction algorithm for LCP arrays. The overhead in time and I/O volume for this extended algorithm over plain suffix array construction is roughly two. The algorithms scale far beyond problem sizes previously considered in the literature (text size of 80 GiB using only 4 GiB of RAM in our experiments).

Datum: Fr, 14 Dez 2012, 14:00

Ort: SR 301

Vortragende(r): Sebastian Lehmann

Inhalt: When drawing planar drawings orthogonally on the grid, one criteria for good readability is to minimize the number of bends on the edges. The general problem is known to be NP-hard, however, we want to find algorithms solving variants efficiently. We present two relaxations of the bend minimization problem that can be solved efficiently. We indroduce an efficient algorithm solving OptimalFlexDraw (bend minimization with cost functions individually per edge) for series-parallel graphs. For the decision problem FlexDraw with positive flexibility (maximum number of bends individually per edge) we implemented and evaluated an efficient testing-algorithm.

Datum: Mi, 12 Dez 2012, 11:30

Ort: SR 236

Vortragende(r): Elias Bordolo

Datum: Fr, 7 Dez 2012, 14:00

Ort: SR 301

Vortragende(r): Simeon Danailov Andreev

Inhalt: Route planning for pedestrians has its own set of problems, similar to routing for vechicles. For one, road network databases generally lack information about street walkways. We show a method for automatic generation of such walkways, based on a road network database. An additional problem are areas where pedestrians can walk freely, for instance plazas, squares and parks. We solve this problem by computing visibility graphs and adding special handling for parks -- areas where footpaths are preferred to walking across.

Datum: Fr, 30 Nov 2012, 14:00

Ort: SR 301

Vortragende(r): Stefan Walzer

Inhalt: In a typical puzzle the goal is to lay pieces into the plane in such a way, that they neatly fit together and tightly fill a given area. We are concerned with something very different: Given a set of pieces, we want to lay copies of them into the plane to achieve a configuration that, although maximal in the sense that no domino can be added without overlapping another one, leaves as much empty space as possible.

Datum: Di, 27 Nov 2012, 14:00

Ort: SR 301

Vortragende(r): Yvonne Braun

Inhalt: In dieser Arbeit wird ein schon vorhandenes Verfahren zur Berechnung der Paarbetweenness PB von je zwei Knoten eines Netzwerkes durch eine Reduktion des Graphen auf seinen 2-Core im Hinblick auf den Speicherverbrauch und die Laufzeit verbessert. Dabei wird das vorhandene Verfahren modifiziert, so dass bei der Paarbetweennessberechnung im 2-Core auch Wege zu Knoten, die außerhalb des 2-Cores liegen berücksichtigt werden. Es wird gezeigt, dass mit Hilfe von vorberechneten Werten auch die Paarbetweennesswerte von Knoten die nicht im 2-Core liegen zu jeder Zeit mit geringem Aufwand berechnet werden können. In der Evaluation zeigt sich, dass das Verfahren für Graphen mit kleinem 2-Core tatsächlich schneller ist und dass durch den geringeren Speicherbedarf auch größere Netzwerke verarbeitet werden können.

Datum: Fr, 23 Nov 2012, 14:30

Ort: SR 301

Vortragende(r): Roland Glantz

Inhalt: We present an algorithm for computing all convex cuts of a plane graph in cubic time. To the best of our knowledge this algorithm is the only one which solves the problem in polynomial time. We first specify a class C of cut-sets and show that C contains the cut-sets of all convex cuts. The number of cut-sets in C is at most twice the number of edges in the graph. We then explain how one can identify the cut-sets in C that give rise to convex cuts.
The class C is defined on general (non-plane) graphs, too. It is interesting in its own right, as it gives rise to cuts that obey a weak form of convexity. In particular, certain shortest paths share exactly one edge with certain cut-sets from C. Moreover, C is dense in that any edge of the graph is contained in at least one cut-set from C.

Datum: Fr, 23 Nov 2012, 14:00

Ort: SR 301

Vortragende(r): Tobias Zündorf

Datum: Fr, 16 Nov 2012, 14:00

Ort: SR 301

Vortragende(r): Friedrich Schroedter, Studienarbeiter

Datum: Di, 13 Nov 2012, 14:00

Ort: SR 301

Vortragende(r): Tobias Columbus

Inhalt: Diese Arbeit beschäftigt sich mit einer sogenannten Beschleunigungstechnik für Dijkstra"s Algorithmus: emph{Contraction Hierarchies}. Wir erarbeiten ein Modell, welches die, in der Praxis gebräuchlichen, heuristischen Contraction Hierarchies erfasst und sich trotzdem für theoretische Betrachtungen eignet. Insbesondere deckt dieses Modell einen unerwarteten Zusammenhang zwischen Contraction Hierarchies und den wesentlich älteren und besser untersuchten Problemen einen gefüllten Graphen mit wenigen Kanten und einen ``elimination tree"" geringer Höhe zu berechnen auf. Diese Beobachtungen ermöglichen die Konstruktion von Contraction Hierarchies mit garantierter maximaler Suchraumgröße O(tw(G) log(n)) bzw. O(sqrt{n}) und garantiertem Platzverbrauch O( tw(G) n log(n) ) bzw. O(n log(n)) für Graphen von Baumbreite tw(G) bzw. Graphen mit Zerlegungen in Separatoren der Größe O(sqrt{n}). Schlussendlich untersuchen wir noch inwieweit lokale Änderungen die Performanz von Distanz-Abfragen in Contraction Hierarchies beeinflussen.

Datum: Fr, 9 Nov 2012, 14:00

Ort: SR 301

Vortragende(r): Ben Strasser

Inhalt: In the past routing in public transportation networks has often focused on vehicles that are always on time. In this talk we introduce a model that incorporates historic delay information using stochastic methods, which allows to define routes with an earliest expected arrival time.
We proceed to develop an algorithm that efficiently determines optimal routes in this model. To this end we first present a novel algorithm to solve the delay-free earliest arrival problem. This algorithm is then expanded to solve the delay-free profile query problem. Based upon this algorithm we then introduce an approach to efficiently solve the proposed stochastic model.
Both of our delay-free algorithm are on par with the current state of the art or outperform it.

Datum: Di, 6 Nov 2012, 14:00

Ort: SR 301

Vortragende(r): Joan Sala Reixach

Datum: Di, 23 Okt 2012, 14:00

Ort: SR 301

Vortragende(r): Daniel Hoske

Inhalt: A k-page book embedding of a graph is a drawing of that graph in a book, with vertices along the book"s spine (a straight line) and edges in k of the book"s pages (half planes with the spine as boundary) such that the edges do not cross. In this talk we consider the problem of determining whether such a drawing exists when the assignment of edges to pages is predetermined. We start by showing that this problem is NP-complete for an unbounded number of pages, even if the edges on each page form a matching, and then solve some special cases. In the case of connected graphs on each page, we provide a linear-time decision algorithm. When the graphs on each page are disjoint perfect matchings, we show that the graph has to be bipartite to be embeddable and give bipartite examples and counterexamples. Following these results, we consider a variation of the problem. If we constrain the vertex orders on the spine by a PQ-tree only containing Q-nodes as inner nodes, embeddability can be decided in quadratic time. At the end we outline the most important open problems for book embedding with fixed page assignments and provide some suggestions on how to approach them.

Datum: Fr, 21 Sep 2012, 14:45

Ort: SR 301

Vortragende(r): Peter Sanders

Datum: Fr, 21 Sep 2012, 11:00

Ort: SR 301

Vortragende(r): David Schoch

Inhalt: Modularity is a quality measure for graph clusterings. It is based on the idea that a random graph is not expected to have a community structure, so the possible existence of communities is revealed by the comparison between the actual density of edges in a subgraph and the expected density if the vertices in the subgraph were attached regardless of community structure. Although the problem of finding the clustering with maximum modularity is NP-complete, many different algorithms were developed which find a good approximation of this maximum in a reasonable time. The studied heuristics were greedy and spectral methods, simulated annealing, extremal optimization and a linear program. The performance of these algorithms were compared on some real and artificial graphs.
Besides the NP-completeness, there are further drawbacks of modularity maximization like the resolution limit and the extreme degeneracy among high--modularity partitions. Because of these problems, a new quality measure was recently introduced.
Theoretical results show, that the maximization of the so called modularity density function can overcome the resolution limit. However there are some major drawbacks for this benefit function, which were found on real graphs.
To identify communities in directed networks, there is a generalized form of modularity called LinkRank which can be considered as the PageRank of links. This generalization is consistent with the original modularity in undirected networks and the modularity optimization methods developed for those networks can be directly applied to directed networks by optimizing this new measure.
In further numerical tests a spectral algorithm was used to compare the three quality measures on artificial graphs with built-in community structure.

Datum: Di, 18 Sep 2012, 17:00

Ort: SR 301

Vortragende(r): Peter Sanders

Datum: Mi, 12 Sep 2012, 11:00

Ort: SR 301

Vortragende(r): Stefan Bechtold

Datum: Mi, 5 Sep 2012, 14:00

Ort: SR 236

Vortragende(r): Florian Ziegler

Inhalt: We present a n-Level Hypergraph Partitioner based on the idea of the n-Level Graph Partitioner by Osipov and Sanders. Given a Hypergraph H we compute a 2-partition P that satisfies a given imbalance constraint. To achieve this we coarsen the original hypergraph in multiple levels. At each level we contract a hyperedge, i.e. merging its hypernodes in one to decrease the number of hypernodes and hyperedges. At the lowest level we construct a bisection $P$ and reverse the coarsening. At each level we additionally refine P. We also implement V-Cycles to improve the quality of P further. We present an extensive experimental evaluation with hypergraph instances widely used in literature, for example parts of the ISPD and MCNC benchmark suites. We compare our system with the state-of-the-art hypergraph partitioners hMETIS and PaToH. Our tuned system achieves hyperedge cuts which are on average as good as those of PaToH. However the runtime of our system is much worse that the one of the competition. Furthermore, our system finds the partition with the smallest hyperedge cut for circa half of the test suite, when compared to the standard presets of hMETIS and PaToH.

Datum: Mi, 5 Sep 2012, 11:00

Ort: SR 236

Vortragende(r): Dr. Pawel Gawrychowski, MPI Saarbrücken

Inhalt: The popularity of the Lempel-Ziv compression scheme (both in practice and in theory) suggest that we should try to develop algorithms operating directly on a compressed representation of the data, hoping to speed-up the computation when the data is highly repetitive. For example, given a Lempel-Ziv compressed text of length N, we should try to design a pattern matching algorithm which doesn"t need to decompress the text (the pattern of length m is assumed to be given explicitly). Such problem has been considered by Farach and Thorup, who designed (randomized) O(nlog^2(N/n)+m) time solution for this problem, where n is the size of the compressed representation. I will show to improve this complexity to (deterministic) O(nlog(N/n)+m) time algorithm. The talk will be based on my ESA"11 paper.

Datum: Di, 7 Aug 2012, 10:30

Ort: SR 301

Vortragende(r): Thomas Sauerwald, Max-Planck-Institut für Informatik Saarbrücken

Inhalt: We consider the problem of balancing load items (tokens) on networks. Starting with an arbitrary load distribution, we allow in each round nodes to exchange tokens with their neighbors. The goal is to achieve a distribution where all nodes have approximately the same number of tokens. For the continuous case where tokens are arbitrarily divisible, most load balancing schemes correspond to Markov chains whose convergence is fairly well-understood in terms of their spectral gap. However, in many applications load items cannot be divided arbitrarily and we need to deal with the discrete case where the load is composed of indivisible tokens. We investigate a natural randomized protocol and demonstrate that there is almost no difference between the discrete and continuous case. Specifically, we show that for any regular network, all nodes have the same load up to an additive constant in the same number of rounds as in the continuous case.

Datum: Fr, 3 Aug 2012, 14:00

Ort: SR 301

Vortragende(r): Jakob von Raumer, Bachelorarbeiter

Inhalt: Kachelungen in der hyperbolischen Geometrie sind nicht nur Forschungsgegendstand von Mathematikern sondern durch das Werk des Künstlers M.C. Escher auch fachfremdem Publikum bekannt. Solche Kachelungen können durch die Wirkung einer Gruppe von Isometrien auf der hyperbolischen Ebene erzeugt werden. Ich habe ein Programm geschrieben, welches Kachelungen erzeugt, die durch die Innenwinkel der polygonalen Kacheln oder durch Charakterisierung der erzeugenden Gruppe festgelegt sind. In meinem Vortrag werde ich zunächst die Grundlagen der hyperbolischen Geometrie zusammenfassen, Fuchssche und Kleinsche Gruppen einführen und dann die Funktionsweise meines Programms erläutern.

Datum: Fr, 20 Jul 2012, 14:00

Ort: SR 301

Vortragende(r): Benjamin Niedermann, Diplomarbeiter

Inhalt: Die automatische Beschriftung von Karten gewinnt zunehmend an Bedeutung. Insbesondere für Karten, die dynamisch erstellt werden oder auf die ausschließlich eine dynamische Sicht zur Verfügung steht, ist eine manuelle Beschriftung nicht möglich. Daher wurde bereits viel Arbeit in die Erforschung automatischer Beschriftung von Karten investiert. In der Diplomarbeit wird der Spezialfall betrachtet, dass man auf eine gegebene Karte mit eingeschränktem Sichtfenster blickt, so dass man nur einen Ausschnitt der Karte sieht. Das Sichtfenster bewegt sich dann entlang einer beliebigen aber fest vorgegebenen Flugbahn und richtet sich dabei bezüglich der Flugbahn aus (z.B. wie im Anwendungsfall eines Navigationsgerätes). Um die Lesbarkeit der Beschriftungselemente zu gewährleisten, wird angenommen, dass diese sich horizontal zum Sichtfenster ausrichten. Folglich kann es dazu kommen, dass sich Beschriftungselemente, während das Sichtfensters sich bewegt, überlappen. Es stellt sich dann die Frage, inwiefern die Beschriftungselemente in optimaler Weise an- und ausgeschaltet werden können, damit keine Überlappungen auftreten. Um diese Frage zu beantworten wird zuerst ein entsprechendes Modell mit passendem Optimalitätsbegriff eingeführt. Mithilfe dieses Modells wird gezeigt, dass die daraus resultierende Problemdefinition NP-schwer ist. Es werden dann Näherungsverfahren zur Lösung dieses Problems vorgestellt.

Datum: Di, 17 Jul 2012, 14:30

Ort: SR 131

Vortragende(r): Alexander Koch

Inhalt: Graphs that are given by an outside-obstacle representation form an interesting superclass of polygon-vertex visibility graphs, which are most studied in the field of visibility problems. We first introduce ray obstacles and compare them to previously defined poylgon and segment obstacle representations (ORs). We define “graph-invariant” maps, which describe possible movements of vertices in a visibility graph, without altering adjacencies. These might be used to continuously transform an outside-OR into a ray OR. We characterize outerplanar graphs that admit a plane outside-OR as chordal outerplane graphs. For general planar graphs we give a set of necessary conditions which we conjecture to also be sufficient.

Datum: Di, 17 Jul 2012, 14:00

Ort: SR 131

Vortragende(r): Georg Osang

Inhalt: Classic results from Ramsey theory state that if certain graphs are made large enough, unavoidable substructures appear. Here we will cover this type of problem for specific graphs when these substructures are certain trees or forests. The following two extremal main problems are presented: For a given family of same-order trees including the star and the path, how large can a tree be that contains none of them as subtree? We show that this value depends heavily on the number of spiders in the family: For a family of $k$-vertex trees consisting of $p$ spiders and a constant number of non-spiders, we constuct a tree of size $2^{\Theta(k\log^{p-1}k)}$ containing no trees from this family, and show that all asymptotically larger trees do contain some of them. Here $\log^{p-1}$ denotes the $p-1$ times iterated logarithm. For a balanced black-white-coloring of the complete bipartite graph $K_{n,n}$, we examine the size of the largest bifork forest contained as subgraph. A bifork is a path of length 2 consisting of a black and a white edge. It is shown that there are at least $(1-\frac{1}{\sqrt{2}})n$ vertex-disjoint biforks all centered in the same partite set, and this is best possible, confirming a conjecture by Tverentina et al. An efficient algorithm finding the largest number is presented.

Datum: Fr, 13 Jul 2012, 13:00

Ort: SR 301

Vortragende(r): Dennis Luxen, Dennis Schieferdecker

Inhalt: We present a fast algorithm with preprocessing for computing multiple good alternative routes in road networks. Our approach is based on single via node routing on top of Contraction Hierarchies and achieves superior quality and efficiency compared to previous methods. The algorithm has neglectable memory overhead.

Datum: Fr, 6 Jul 2012, 14:00

Ort: SR 301

Vortragende(r): Christian Schulz

Datum: Fr, 29 Jun 2012, 14:00

Ort: SR 301

Vortragende(r): Shunsuke Inenaga, Kyushu University

Inhalt: Subsequence pattern matching problems on compressed text were first considered by Cegielski et al., where the principal problem is: given a string T represented as a straight line program (SLP) of size n and an uncompressed string P of length m, compute the number of minimal subsequence occurrences of P in T. We present an O(nm)-time algorithm for solving all variations of the problem introduced by Cegielski et al.. This improves the previous best known algorithm of Tiskin, which runs in O(nmlog m) time. We further show that our algorithms can be modied to solve a wider range of problems in the same O(nm) time complexity, and present the first matching algorithms for patterns containing VLDC (variable length don't care) symbols, as well as for patterns containing FLDC (fixed length don't care) symbols, on SLP compressed texts.

Datum: Fr, 22 Jun 2012, 14:00

Ort: SR 301

Vortragende(r): Marcel Birn, Diplomarbeiter

Inhalt: The computation of matchings has applications in the solving process of a large variety of problems, e.g. as part of graph partitioners. We present and analyze three sequential and two parallel approximation algorithms for the cardinality and weighted matching problems. One of the sequential algorithms is based on an algorithm by Karp and Sipser to compute maximal matchings. Another one is based on the idea of locally heaviest edges by Preis. The third sequential algorithm is a new algorithm based on the computation of maximum weighted matchings of trees spanning the input graph. We show for two of these algorithms that the runtime for slight variations of them is expected to be linear. However the experimental results suggest that this is also the case for the unmodi?ed versions. The comparison with other approximate matching algorithms show that the computed matchings have a similar quality or even the same quality. On the other hand two of our the algorithms are much faster. For two of the sequential algorithms we show how to turn them into parallel matching algorithms. We show that for a simple non optimal partitioning of the input graphs speedups can be observed using up to 1024 processors. For certain kinds of input graphs we see a good scaling behaviour.

Datum: Do, 21 Jun 2012, 12:00

Ort: SR 301

Vortragende(r): Jörg D. Weisbarth

Inhalt: Ein r-Shortest Path Cover (SPC) eines gewichteten Graphen ist eine Knotenteilmenge S des Graphen, die die nachfolgende Eigenschaft erfüllt: Zwischen je zwei Knoten, mit mindestens dem Abstand r, enthält wenigstens einer der kürzesten Wege dazwischen einen Knoten aus S. Falls die Knoten eines solchen SPCs hinreichend dünn im Graphen verteilt sind, können damit einige bekannte Algorithmen zur Suche von kürzesten Wegen auf gewichteten Graphen beschleunigt werden. Diese Arbeit beschäftigt sich in erster Linie mit der Berechnung von möglichst kleinen r-SPCs für bestimmte, eingeschränkte Graphklassen. Dabei werden für Wege, Bäume und Kreise effizient optimale Lösungen gefunden und für außenplanare Graphen Approximationen. Für allgemeinere Graphklassen wird gezeigt, dass das Finden einer Lösung schwierig ist, da das Problem im Allgemeinen NP-vollständig ist.

Datum: Do, 21 Jun 2012, 11:30

Ort: SR 301

Vortragende(r): Andreas Bauer

Inhalt: Viele Menschen nutzen heute technische Hilfsmittel, um ihre Reiseroute zu planen. Für Autos sind Navigationsgeräte verbreitet, und immer mehr Menschen nutzen das Internet für die Fahrplanauskunft. Die meisten Algorithmen, die optimale Routen berechnen, arbeiten nur auf einem dieser Netzwerke. Für die multimodale Routenplanung, wenn also verschiedene Transportmöglichkeiten genutzt werden sollen, müssen diese adaptiert werden. Desweiteren hängt, vor allem bei öffentlichen Verkehrsmitteln, die kürzeste Reisezeit vom Abfahrtszeitpunkt ab. Die Abfahrtszeit ist jedoch selbst ein wichtiges Kriterium für die beste Route, weswegen eine Profilsuche sinnvoll ist, d.h. die kürzeste Reisezeit für jeden möglichen Abfahrtszeitpunkt zu finden. In dieser Arbeit werden zwei Algorithmen vorgestellt und getestet, die solche Profilsuchen für multimodale Netzwerke ausführen. Wir vergleichen diese Algorithmen mit einem hypothetischen Algorithmus, der alle relevanten Abfahrtszeiten im voraus kennt und für jeden dieser Zeiten eine multimodale Version von Dijkstra's Algorithmus ausführt. Wir erreichen dann einen Speedup von bis zu einer Größenordnung.

Datum: Mo, 18 Jun 2012, 13:00

Ort: SR 301

Vortragende(r): Nodari Sitchinava

Inhalt: Parallel External Memory (PEM) model was introduced to capture the cache-based nature of modern multicore architectures. The algorithms designed in the PEM model take advantage of the fast private caches of individual cores. In this talk I will provide an overview of the current state of the art in algorithm design in the PEM model and present our latest results in designing the parallel buffer tree in the PEM model, the only data structure that is both parallel and cache-efficient.

Datum: Fr, 1 Jun 2012, 14:00

Ort: SR 301

Vortragende(r): David Oertel

Inhalt: Das Problem des Ausbaus von Hochspannungsnetzen in einem vereinfachenden mathematischen Modell ist wie folgt definiert. Gegeben ein Hochspannungs-Netz aus Erzeugern und Verbrauchern (abstrahiert als Knoten), die durch Stromleitungen (Kanten) verbundensind: An welchen Stellen sollen mit möglichst geringen Kosten neue Leitungen eingefügt werden, sodass vorgegebene maximale Belastungender Leitungen nicht überschritten werden? Dieses Problem ist in der ursprünglichen Formulierung als mixed-integer non-linear programNP-schwer, da es als Untermenge das Steinerbaumproblem enthält.Durch Gebrauch der Theroie über elektrische Netzwerke wird gezeigt, warum das Problem weiterhin NP-schwer ist, wenn die Unterklasse vonSteinerbäumen ignoriert wird, indem nur (hochgradig) zusammenhängende Graphen betrachtet werden und der Fokus auf die Einhaltung dermaximalen Kantenbelastung gelegt wird. Diese Einschränkung spiegelt den realistischeren Fall wider, wenn ein lange existierendesHochspannungsnetz wegen eines steigenden zukünftigen Strombedarfs erweitert werden muss. Die algorithmische Schwierigkeit wirdbewiesen, indem gezeigt wird, dass dieses Problem algorithmisch äquivalent zu $3$-SAT ist.Darüberhinaus wird gezeigt, wie viel Aufwand für Berechnung und Implementierung wirklich nötig ist, um realistische Szenarios in der Praxis zu lösen.

Datum: Di, 22 Mai 2012, 17:30

Ort: HS -101

Vortragende(r): Ryan Martin, Iowa State University

Inhalt: The Boolean lattice of dimension two, also known as the diamond, consists of four distinct elements with the following property: $A\subset B,C\subset D$. A diamond-free family in the $n$-dimensional Boolean lattice is a subposet such that no four elements form a diamond. Note that elements $B$ and $C$ may or may not be related. There is a diamond-free family in the $n$-dimensional Boolean lattice of size $(2-o(1)){n\choose\lfloor n/2\rfloor}$. In this paper, we prove that any diamond-free family in the $n$-dimensional Boolean lattice has size at most $(2.25+o(1)){n\choose\lfloor n/2\rfloor}$. Furthermore, we show that the so-called Lubell function of a diamond-free family in the $n$-dimensional Boolean lattice is at most $2.25+o(1)$, which is asympotically best possible.

Datum: Di, 22 Mai 2012, 14:30

Ort: SR -120

Vortragende(r): Neil Jami, Diplomarbeiter

Inhalt: In der Kartographie ist das Beschriften von Karten, auch Labeling genannt, eines der klassischen Probleme. Gegeben ist eine Menge von n Punkten und eine Beschriftung (Label) für jeden Punkt. Ziel besteht darin, die Labels so an ihren Punkten zu platzieren, dass sich keine zwei Labels überlappen. Im klassischen Labeling Problem werden die Label innerhalb der Karte so positioniert, das jedes Label dem entsprechendem Punkt berührt. Für dieses Modell gibt es Instanzen bei denen nicht alle Labels konfliktfrei zeichenbar sind oder wichtige Informationen durch Labels verdeckt sind. Deshalb wurde das Boundary Labeling Modell eingeführt, in dem die Labels außerhalb der Karte und entlang einer Grenze platziert werden. Jeder Punkt ist dann zu einem Label mit einer Verbindungslinie, die Leader genannt wird, verbunden. In diesem Vortrag wird das Boundary Labeling Problem untersucht. Die Labels werden rechts von der Karte platziert und durch achsenparallele Leader verbunden. Im klassischen Boundary Labeling sind die Labels entlang einer vertikalen Grenze positioniert. Hier betrachten wir hingegen eine konvexe Grenze, die aus mehreren Kanten besteht. Mit diesem neuen Modell können spezifischere Grenzen der Karte für Boundary Labeling genutzt werden. Es werden verschiedene Varianten dieses Labelingsmodells vorgestellt, und effiziente Algorithmen beschrieben, die kreuzungfreie Labelings minimaler Leaderlänge erzeugen.

Datum: Di, 22 Mai 2012, 14:00

Ort: SR -120

Vortragende(r): Jonathan Rollin, Studienarbeiter

Inhalt: Ein gegebener Graph soll durch Einfügen neuer Kanten so erweitert werden, dass bestimmte zusätzliche Eigenschaften erfüllt werden. Genauer gesagt soll hier die Planarität eines Graphen erhalten bleiben, wenn durch zusätzliche Kanten 3-Regularität erreicht wird. Darüber hinaus soll wenn möglich auch der Zusammenhang verstärkt werden. Es stellt sich heraus, dass es NP-schwer ist zu entscheiden, ob eine solche Menge von neuen Kanten für einen gegebenen planaren Graphen existiert. Das Problem bleibt sogar dann NP-schwer, wenn als Eingabeinstanzen nur bereits 2-fach zusammenhängende Graphen betrachtet werden. Beschränkt man sich jedoch darauf, dass die neuen Kanten nur innerhalb der Facetten einer gegebenen planaren Einbettung eingefügt werden dürfen, so reduziert sich die Komplexität des Problems deutlich. Es wird gezeigt, dass sich dieses Problem auf ein Matchingresultat reduzieren lässt. Die Existenz einer solchen 3-regulären (und 2-fach zusammenhängenden) Erweiterung ist äquivalent zur Existenz eines Matchings in einem bestimmten Graphen und somit effizient berechenbar. Für diesen Fall wird zudem ein Algorithmus zur Berechnung einer 3-regulären und 2-fach zusammenhängenden Erweiterung vorgestellt.

Datum: Fr, 18 Mai 2012, 14:00

Ort: SR 301

Vortragende(r): Daniel Patejdl

Inhalt: Graphen eignen sich nicht nur zur algorithmichen Lösung von Problemen, sondern auch dazu, in visualisierter Form Zusammenhänge für das menschliche Auge darzustellen. Eine Variante der Darstellung ist die Einbettung von Graphen in Gitter. Das Standard-Gitter ist das orthogonale Gitter, welches durch horizontal und vertikal verlaufende Linien konstruiert wird. In dieser Arbeit werden Einbettungen von Graphen auf Nichtstandard-Gitter betrachtet, die bisher nur rudimentär erforscht sind. Zum einen das Bienenwabengitter, eine Anordnung von regulären, zusammenhängenden Sechsecken, auf dem verschiedene Algorithmen zum Zeichnen von Bäumen präsentiert werden. Die von den Algorithmen auf dem Gitter gezeichneten Bäume werden anschließend hinsichtlich ihres Platzverbrauchs, ein häufig auftretendes Optimierungskriterium, analysiert. Zum anderen wird ein regulär trianguliertes Gitter, auch hexagonales Gitter genannt, thematisiert. Das hexagonale Gitter kann durch eine Erweiterung des Bienenwabengitters um Diagonalen konstruiert werden. Durch eine Scherung des Gitters erhält man ein Gitter, welches strukturelle Ähnlichkeiten zum orthogonalen Gitter aufweist. Diese Ähnlichkeiten erlauben es, bekannte algorithmische sowie komplexitätstheoretische Ergebnisse vom orthogonalen auf das hexagonale Gitter zu übertragen. Es wird unter anderem ein effizienter Algorithmus vorgestellt, der zu bestimmten 4-planaren Graphen eine Einbettung in eine gegebene Punktmenge auf dem hexagonalen Gitter berechnet. Dabei wird die Einbettung so gewählt, dass alle Kanten durch kürzeste Wege realisiert sind. Des Weiteren wird gezeigt, dass das Problem, welches der Algorithmus für spezielle Graphen effizient löst, im Allgemeinen NP-schwer ist.

Datum: Mi, 16 Mai 2012, 14:00

Ort: SR 301

Vortragende(r): Christos Zaroliagis, University of Patras

Inhalt: An ad-hoc mobile network is a collection of mobile hosts with wireless network interfaces forming a temporary network without the aid of any established infrastructure or centralized administration. In an ad-hoc network two hosts that want to communicate may not be within the wireless transmission range of each other, but could communicate if other hosts between them are also participating in the ad-hoc network and are willing to forward packets for them. The most common way to establish communication is to form paths of intermediate nodes (hosts), where it is assumed that there is a link between two nodes if the corresponding hosts lie within one another's transmission radius and hence can directly communicate with each other. In wide area ad-hoc networks, however, a sufficiently long communication path is difficult to establish and/or maintain. Single link failures, happening when a small number of users that were part of the communication path move in a way such that they are no longer within the transmission range of each other, make the path invalid. In this lecture, we shall investigate a different approach to establish basic communication in ad-hoc mobile networks. The main idea is to take advantage of the mobile hosts natural movement by exchanging information whenever mobile hosts meet incidentally. In particular, two protocols will be presented that are based on the semi-compulsory approach, according to which a small part of the mobile users that moves in a predetermined way is used as an intermediate pool for receiving and delivering messages. The practical assessment of the protocols will be also discussed.

Datum: Di, 15 Mai 2012, 14:00

Ort: SR -120

Vortragende(r): Philipp Schneider, Studienarbeiter

Inhalt: Eine spezielle Sorte von Netzwerkerweiterungsproblemen, nämlich die Frage, wie man einen gegebenen Punkt (Feed-node) innerhalb einer Facette eines Netzwerkes, dargestellt als Rand eines einfachen Polygons, mit diesem sinnvoll verbinden kann, wurde von Aronov et al. behandelt. Aronov et al. ziehen die Streckung als Maß der Güte einer oder mehrerer Verbindungen (Feed-links) des Punktes mit dem Rand des Polygons heran. Dieses Gütemaß spiegelt den relativen Umweg wieder, den man über das Netzwerk und den Feed-link im Vergleich zum direkten Weg nehmen muss. Aronov et al. Stellen heraus, dass die Frage nach der optimalen Platzierung von mehr als einem Feed-link in einfachen Polygonen ungeklärt bleibt. Wir werden einen Spezialfall dieses Problems lösen, nämlich die effiziente optimale Platzierung von zwei Feed-links bezüglich einer gegebenen, endlichen Menge von Sites. Außerdem werden wir eine abgeänderte Problemstellung betrachten, in der rektilineare, einfache Polygone gegeben sind (das sind einfache Polygone mit lediglich horizontalen und vertikalen Kanten), für die wir rektilineare Feed-links (das sind kürzeste Wege aus lediglich horizontalen und vertikalen Kanten) vom Feed-node an den Rand des Polygons suchen, so dass die Streckung gemessen mit der L1-Metrik minimal wird.

Datum: Mo, 14 Mai 2012, 10:00

Ort: SR 236

Vortragende(r): Roger Wattenhofer, ETH Zürich

Inhalt: The title of my presentation is a motto originally coined in urban design about 100 years ago, but used in various different contexts since. The motto can also be applied to many areas in computer science. For instance, in computational game theory, each agent tries to maximize his/her own (local) benefit, and we analyze the (global) social welfare. Also, computer architecture is designed for locality of reference. Recently, the distributed computing community has made tremendous progress towards understanding the complexity of distributed message passing algorithms. In networks, a rich selection of upper and lower bounds regarding how much time it takes to solve or approximate a problem have been established; we now have a good understanding how local actions and global goal influence each other. This distributed complexity theory may ultimately help to give the "think global, act local" motto a mathematical foundation. In my talk I will introduce the message passing model, present a few selected results, mention prominent open problems, and discuss some of the most exciting future research directions. Upcoming applications may not necessarily lie in computer science but rather in other areas that deal with networked systems, e.g. biology or social sciences.

Datum: Fr, 11 Mai 2012, 14:00

Ort: SR 301

Vortragende(r): Morteza Monemizadeh

Inhalt: Recent developments \cite{BSS08,CSS09,HKNO09,NO08} in the area of testing properties for classes of bounded-degree graphs with an excluded minor propose a new technique called \textit{partitioning oracles}. A partitioning oracle explores local neighborhoods of sampled vertices and using this, answers queries about a global partition that breaks the graph into small connected components by removing only a small fraction of the edges. We take the idea of partitioning oracles as the first step to connect property testing algorithms to streaming algorithms. In this paper, we focus on the \emph{Euclidean facility location problems} as a test case. Given a point set $P = \{p_1, \dots, p_n\}$ of size $n$ in the plane $[\Delta]^2=\{0,1,\dots,\Delta\}^2$ and $f \in \Re^+$, the facility location problem is to find a set $F \subseteq [\Delta]^2$ of facilities such that % \begin{displaymath} \mathrm{cost}(P,F)=\sum_{p \in P} \dist(p,F)+|F|\cdot f \end{displaymath} % is minimized, where $\dist(p,F)=\min_{q \in F} \dist(p,q)$ is the distance of $p$ to the nearest facility in $F$. We show that there is a partitioning $\IN$ of the plane into regions (called isolated neighborhoods) by removal of small regions (called borders) surrounding isolated neighborhoods. By putting $\epsilon\cdot |F|$ artificial facilities inside the borders of the regions of $\IN$ we are able to disconnect each isolated neighborhood from its outside and by solving the facility location problem inside each isolated neighborhood and its border and taking the union of the solutions we find a new PTAS for this problem. Then we show that there is an oracle for the partitioning $\IN$ which can be implemented in the turnstile streaming model using $\mathrm{poly}(\epsilon^{-1}\log\Delta)$ space. This in turn gives a $(1+\epsilon)$-approximation to the cost of the Euclidean facility location problem in the turnstile streaming model using $\mathrm{poly}(\epsilon^{-1}\log\Delta)$ space solving this major open problem in the streaming model after seven years.

Datum: Fr, 27 Apr 2012, 14:30

Ort: SR 301

Vortragende(r): Roman Zubkov, Bachelorarbeiter

Inhalt: In dieser Arbeit wird gezeigt, wie die Beschreibung einer Route im Straßennetz komprimiert dargestellt werden kann. Ein Szenario wird zugrunde gelegt, indem ein Klient (z. B. ein Navigationsgerät) eine Anfrage nach einer Route von einem Startpunkt zu einem Zielpunkt an einen Server sendet. Der Server besitzt statistische Verkehrsinformationen, mit denen er eine optimale Route berechnet. Er komprimiert sie und sendet sie an den Klienten. Um die Route möglichst kompakt zu komprimieren, wird sie in möglichst große eindeutige kürzeste Pfade zerlegt. Der Knoten, an dem einer dieser kürzesten Pfade endet und der nächste kürzeste Pfad beginnt, wird Viaknoten genannt. Die Sequenz der Viaknoten bildet die komprimierte Route. Um die Viaknoten zu finden, werden vier verschiedene Strategien ausgearbeitet. Die erste Strategie ist eine Modifikation des Algorithmus von Dijkstra, die einen maximalen eindeutigen kürzesten Präfixpfad eines Pfades berechnet. Zur Beschleunigung der Kompression und Dekompression wird eine Contraction Hierarchie (CH) verwendet. Mit Hilfe einer modifizierten Punkt-zu-Punkt-Anfrage der CH werden drei weitere Strategien entwickelt. Zu jeder Kompressionsstrategie werden Experimente durchgeführt und evaluiert. Die Kompressionsrate bleibt dabei unter 1,7% und die Kompressionszeit bei der schnellsten Strategie unter 50 ms, selbst bei größtmöglichen, kürzesten Routen im deutschen Straßennetz. Diese Arbeit greift die Idee von Viaknoten von G. V. Batz et al. auf und baut sie aus. Zusätzliche Algorithmen werden entwickelt, die Kompressionsverfahren werden an die CH angepasst, Beweise für theoretische Aussagen werden geliefert und alle Algorithmen werden implementiert und evaluiert.

Datum: Fr, 20 Apr 2012, 14:00

Ort: SR 301

Vortragende(r): Fabian Fuchs, Diplomarbeiter

Inhalt: In Drahtlosnetzwerken steht üblicherweise nur eine begrenzte Menge Energie zur Verfügung. Da die Kommunikation in Drahtlosnetzwerken einen Großteil der Energie verbraucht, wurden in den letzten Jahren viele Möglichkeiten untersucht Kommunikation effizienter zu gestalten - vor allem in Bezug auf Energie- und Störungsminimierung. Eine der Möglichkeiten ist das Einteilen der Übertragungen in Zeitslots (sog. TDMA Schedules). In dieser Arbeit vergleichen wir den erreichbaren Datendurchsatz für Medienzugriff via TDMA Schedules mit dem Medienzugriff mittels des CSMA/CA Mechanismus mit Hilfe des Netzwerksimulators ns-3 und untersuchen die Auswirkungen eines bidirektionalen Interferenzmodells auf die Effizienz der TDMA Schedules. Eine andere Möglichkeit den Energieverbrauch sowie Störungen zu reduzieren bietet Topologiekontrolle. Hierbei werden die Kommunikationsverbindungen des Netzwerks auf eine Auswahl beschränkt und (wenn möglich) die Sendeleistung reduziert. Viele Algorithmen für Topologiekontrolle wurden bisher hauptsächlich theoretisch betrachtet. In dieser Arbeit werden die Algorithmen in Hinblick auf Datendurchsatz sowie Energieverbrauch mittels des Netzwerksimulators ns-3 untersucht.

Datum: Fr, 23 Mär 2012, 14:00

Ort: SR 301

Vortragende(r): Christian Wellenbrock, Studienarbeiter

Inhalt: Bei der Visualisierung großer Graphen stoßen automatische Layoutalgorithmen schnell an ihre Grenzen. Will man bestimmte Strukturen, Subgraphen oder Symmetrien hervorheben, müssen oft große Teile des Graphen manipuliert werden. Wir betrachten konkret das Problem, in einem Graphen Platz für einen vorgegebenes Polygon zu schaffen, um dort etwa einen weiteren Teilgraphen einzufügen. Wir suchen also nach Einbettungen, in denen in einer bestimmten Facette Platz für dieses Polygon ist. Um die Wiedererkennbarkeit des ursprünglichen Layouts zu erhöhen, versuchen wir dabei die mittlere Längenänderung aller Kanten zu minimieren. Wir zeigen das dieses Problem in drei Varianten NP-schwer ist und stellen anschließend zwei heuristische Algorithmen zur approximativen Lösung vor.

Datum: Di, 20 Mär 2012, 14:00

Ort: SR 301

Vortragende(r): Christof Doll, Diplomarbeiter

Inhalt: Die Diplomarbeit beschäftigt sich mit automatisch generierten Layouts von Argumentkarten. Diese stellen Argumente einzelner Texte oder ganzer Debatten sowie deren Beziehungen zueinander als Graphstruktur dar. Sie finden hauptsächlich innerhalb der Geisteswissenschaft ihre Anwendung. Die Arbeit beginnt mit einer empirischen Analyse der graphentheoretischen Eigenschaften von Argumentkarten. Darauf aufbauend definieren wir die Anforderungen an Layouts von Argumentkarten sowie die zu optimierenden Kriterien. Grundlegend sollen die gewünschten Layouts orthogonale Aufwärtszeichnungen sein. Daneben fordern wir, dass die Zeichenfläche in disjunkte Spalten unterteilt ist, denen dann einzelne oder mehrere Knoten zugeteilt werden. Daher bezeichnen wir diese Layouts als Spalten-basiert. Bei der Erstellung der Layouts möchten wir die Kreuzungs- und Knickzahl, die Gesamtkantenlänge sowie die Distanz von Quellen und Senken zur äußeren Facette minimieren. Im Anschluss stellen wir einen auf dem Topology-Shape-Metrics-Framework basierender Algorithmus vor, der derartige Layouts berechnet. Dabei definieren wir die drei Schritte des Frameworks formal und untersuchen sie einzeln in Bezug auf ihre Komplexität. Der Topology- und Metrics-Schritt erweisen sich als NP-vollständig, während wir für den Shape-Schritt die NP-Vollständigkeit nur vermuten können. Aus diesen Gründen werden die wichtigsten Schritte der Layoutberechnung heuristisch gelöst. In einer anschließenden Untersuchung der berechneten Layouts stellen wir jedoch fest, dass die Optimierungskriterien hinreichend gut minimiert werden. Darüber hinaus überzeugen diese Layouts auch aufgrund ihrer Ästhetik und der übersichtlichen Struktur.

Datum: Fr, 2 Mär 2012, 14:00

Ort: SR 301

Vortragende(r): Maximilian Schuler, Bachelorarbeiter

Inhalt: Viele modernen Graphpartitionierungsalgorithmen verwenden ein Mehrlevelverfahren, das aus drei Phasen besteht: Zunächst wird eine Hierarchie von Schrittweiße gröberen Graphen erstellt, woraufhin der gröbste Graph initial partitioniert wird und zuletzt wird für jeden feineren Graphen die Partitionierung verbessert. Da die Vergröberungsphase essentiell für ein gutes Ergebnis ist, werden in diesem Vortrag neue Techniken vorgestellt die in dieser Phase des Algorithmuses anwendung finden. Hierbei liegt das Hauptaugenmerk auf der Konstruktion neuer Kantenbewertungsfunktionen und der Analyse und dem Entwurf eines neuen approximativen Paarungsalgorithmuses. Alle Ergebnisse werden mithilfe des Merhlevel-Graphpartitionierers KaFFPa ausgewertet. Es wird sich zeigen, dass gerade bei der Partitionierung von sozialen Netzwerken signifikante Verbesserungen der Partitionisqualität erziehlt werden können.

Datum: Di, 7 Feb 2012, 14:30

Ort: SR 301

Vortragende(r): Roland Gröll, Studienarbeiter

Inhalt: Die Corestruktur hat sich als interessantes Maß in der Netzwerkanalyse herrausgestellt. In dieser Studienarbeit wurde untersucht, wie man die Corestruktur eines Graphen mit möglichst wenigen Kantenadditionen verbessern kann. Es stellte sich heraus, dass es möglich ist in polynomieller Zeit den gesamten Graphen in den k-Core zu bringen. Schränkt man die Menge der Knoten, die man in einem gewissen Core haben möchte jedoch auf eine vorher festgelegte Teilmenge ein, ist das Problem NP-schwer, selbst für den k-core mit k = 3, jedoch polynomiell lösbar für kleinere k.

Datum: Di, 7 Feb 2012, 14:00

Ort: SR 301

Vortragende(r): Jan-Christoph Athenstädt, Studienarbeiter

Inhalt: Die Studienarbeit stellt ein Verfahren zur Visualisierung von großen, geclusterten Graphen (> 10.000 Knoten) vor. Zunächst wird ein 2D-Layout unter Berücksichtigung der bestehenden Hierarchie aus Clustern generiert, welches dann im zweiten Schritt in 3D mit Hilfe einer Landschafts-Metapher dargestellt wird. Für das 2D-Layout wird ein kräftebasiertes Verfahren auf Basis des Fruchterman-Reingold-Algorithmus verwendet. Ziel ist es hierbei, sowohl einzelne Knoten und Kanten als auch die Gesamtstruktur und die verschiedenen Clusterebenen darzustellen. Die 3D-Landschaft wird mit Hilfe eines Gauss-Filters als Höhenfeld über dem 2D-Layout generiert. Dabei können verschiedene Charakteristiken des Layouts, wie zum Beispiel die Knotendichte oder der durchschnittlichen Knotengrad als Höheninformation dargestellt werden. Der ursprüngliche Graph wird anschließend über die Landschaft gelegt, wobei geradlinige Kanten die Knoten verbinden.

Datum: Fr, 27 Jan 2012, 14:00

Ort: SR 301

Vortragende(r): Jan-Ole Sasse, Diplomarbeiter

Datum: Di, 24 Jan 2012, 14:30

Ort: SR 301

Vortragende(r): Geraud Oscar Fofie Lafou, Diplomarbeiter

Inhalt: In dieser Arbeit geht es darum, zu untersuchen, welcher Clusteringalgorithmus bessere Clusterungen liefert. Dabei werden besonders Clusteringalgorithmen betrachtet, die mehrere Clusterungen verschiedener Grobheit liefern. Die Algorithmen werden miteinander anhand von Zufallsgraphen verglichen. Der Vergleich besteht darin, zu untersuchen, wie gut jeder Algorithmus die Referenzclusterungen in Zufallsgraphen wiedererkennt. Dafür werden Zufallsgraphen erzeugt, die mehrere Clusterungen enthalten. Die Clusterungen in Zufallsgraphen enthalten sich gegenseitig (hierarchische Clusterungen) oder überlappen sich gegenseitig (sich überlagernde Clusterungen). Ein großer Teil der Arbeit besteht darin, einen effizenten Algorithmus zu entwickeln, der solche Zufallsgraphen erzeugt.

Datum: Di, 24 Jan 2012, 14:00

Ort: SR 301

Vortragende(r): Tobias Haaß

Inhalt: In der Bachelorarbeit geht es um das Visualisieren standortgebundener Infrastrukturprojekte, die als soziales Netzwerk modelliert werden. Zunächst wird das Projekt als Graph modelliert. Für die Zeichnung wird jedem Knoten eine initiale Position zugeordnet, die von seinem Herkunftsort aus der Realität abhängt. Bei den betrachteten Projekten hat sich gezeigt, dass sich viele Akteure am Projektstandort ansammeln. Um für eine bessere Übersicht zu sorgen, wird die nähere Umgebung um den Standort entzerrt. Des Weiteren werden Knotenüberlappungen mit einem kräftebasierten Algorithmus aufgelöst. Abschließend werden für jeden Knoten Beschriftungen eingefügt und eine Position für diese berechnet. Um die Struktur des Graphen zu analysieren wird das Projekt als Correlation-Clustering Problem betrachtet und ein ganzzahliges lineares Optimierungsproblem gelöst.

Datum: Fr, 20 Jan 2012, 14:00

Ort: SR 301

Vortragende(r): Michael Hamann, Bachelorarbeiter

Inhalt: Die Qualitätsbewertung von Clusterungen ist eine schwierig zu formalisierende Aufgabenstellung, was sich insbesondere in der Existenz einer Vielzahl von verschiedenen Qualitätsmaßen ausdrückt. Der schnittbasierte Cut-Clustering-Algorithmus von Flake et al. erzeugt abhängig von einem Parameter hierarchisch verschachtelte Clusterungen. Diese zeichnen sich durch eine Qualitätsgarantie bezüglich des Maßes intra-cluster-Expansion aus, welches im allgemeinen schwer zu berechnen ist. Diese Arbeit stellt ein Verfahren vor, das systematisch alle verschachtelten Clusterungen, die mit Hilfe des Cut-Clustering-Algorithmus erzeugt werden können, findet und untersucht experimentell die Aussagekraft der gegebenen Qualitätsgarantie im Vergleich mit trivialen Schranken. Des weiteren bewertet sie die Qualität der Clusterungen bezüglich des gängigen Maßes Modularity und vergleicht die Ergebnisse mit jenen eines modularity-basierten Greedy-Algorithmus, der im Gegensatz zum Cut-Clustering-Algorithmus explizit versucht Modularity zu optimieren.

Datum: Mi, 21 Dez 2011, 11:30

Ort: SR 236

Vortragende(r): Samitha Samaranayake, UC Berkeley

Inhalt: Optimal routing in transportation networks can be a challenging problem when considering the stochastic nature of link travel-times. Therefore, it is common to use the expected value of link travel-times as a sufficient statistic and ignore the variance, even though route reliability is an important decision factor in many applications. In this presentation, we consider the following optimality criterion: maximizing the probability of arriving on time at a destination given a departure time and a time budget, and show how to efficiently generate an optimal routing policy. One of the complexities of this problem is the fact that the optimal routing policy could contain loops. We propose a dynamic programming based solution that finds an optimal policy by first computing an optimal order in which to solve the dynamic program. Experimental results are presented for practical scenarios in the San Francisco Bay Area.

Datum: Fr, 2 Dez 2011, 14:00

Ort: SR 301

Vortragende(r): Jonathan Dimond, Studienarbeiter

Inhalt: Mit einer immer stärker vernetzten Welt steigt das Bedürfnis, aus veschiedensten Netzwerken Informationen zu gewinnen. In den letzten Jahren gewann das Problem des Community Clusterings zunehmend an Bedeutung. Für riesige Graphen mit Milliarden von Knoten kann dies eine unlösbare Aufgabe bedeuten. Wir betrachten das inverse Problem. Für gegebene Knoten soll ein Subgraph extrahiert werden, der eine sinnvolle Community darstellt. Wir betrachten dafür Random Walks und eine verwandte aber neuartige Methode, die wir Similarity Propagation nennen, und analysieren ihre Güte anhand von Conductance. Zusätzlich analysieren wir, wie sich für dieses Problem etablierte Verfahren für einen dynamischen Graphen anpassen lassen. Darüber hinaus stellen wir einen Graph Generator vor, der in der Lage ist, effizient riesige Graphen mit günstigen Eigenschaften wie Power-Law Kantengradverteilungen und Community-Struktur zu generieren.

Datum: Mi, 23 Nov 2011, 13:00

Ort: SR 236

Vortragende(r): Prof. Lawrence Mandow, Universidad de Malaga (Spain)

Inhalt: The shortest path problem has been widely studied in the past, and a variety of algorithms have been proposed. Most of them are variants of Dijkstra’s or A* algorithms. Many recent studies are focused on their application in car navigation systems. These software systems give the best route to a destination point according to a single criterion, like the minimization of time. Additional criteria, like distance or economic cost, are considered in general only in a weighted form. The Multiobjective Shortest Path Problem explicitly considers the simultaneous optimization of several objectives. The problem no longer has a single optimal solution but a set of efficient, or Pareto-optimal solutions. The number of efficient solutions is known to grow exponentially with graph size in the worst case. However, in certain classes of problems the number of efficient solutions can be shown to grow only polynomially with goal depth in the worst case. Several extensions to Dijkstra’s or A* algorithm have been devised to solve the problem. The former’s most known extension is due to Martins. This talk covers the proposed extensions of A* to multiobjective search, namely MOA*, NAMOA*, and Tung & Chew’s algorithm. Formal properties and empirical evaluations will be discussed. The use of adequate heuristics can be very beneficial in certain cases in terms of space and time performance. An overview of key aspects about heuristics in multiobjective A*-like algorithms will be provided, and their application to route planning in road maps will be discussed.

Datum: Di, 22 Nov 2011, 13:30

Ort: SR 301

Vortragende(r): Heiner Zille, Bachelorarbeiter

Inhalt: Diese Arbeit beschäftigt sich mit der Berechnung möglichst einfacher Routen als Alternativen zu kürzesten Routen. Im Gegensatz zu früheren Arbeiten sollen einfachste Routen unter der Nebenbdingung gefunden werden, dass diese eine gewisse Maximallänge im Vergleich zum kürzesten Weg nicht überschreiten. Die entwickelten Verfahren wurden implementiert und evaluiert mit Hinsicht auf den Anwendungsfall: Schematische Darstellung von Routen.

Datum: Fr, 11 Nov 2011, 13:15

Ort: SR 301

Vortragende(r): Moritz Baum, Diplomarbeiter

Inhalt: Viele bekannte Beschleunigungstechniken zur Routenplanung gewähren Freiheitsgrade in der konkreten Umsetzung ihrer Vorberechnung, deren Ausfüllung großen Einfluss auf die Performanz späterer Kürzeste-Wege-Anfragen haben kann. Im Falle von Arc-Flags besteht dieser Freiheitsgrad in der Wahl einer Partition des Eingabegraphen. Ein gängiges Maß zur Bewertung der Qualität einer solchen Partition ist die Betrachtung der erwarteten Suchraumgröße einer zufälligen Anfrage. Die Berechnung einer Partition, die den erwarteten Suchraum minimiert, ist im Allgemeinen $\mathcal{NP}$-schwer. Ausgehend von diesem Resultat liegt der Schwerpunkt dieser Arbeit auf einer ausführlichen theoretischen Untersuchung dieses Problems. Zunächst wird dazu der Einfluss verschiedener eingeschränkter Graphklassen auf die Schwierigkeit der Berechnung einer optimalen Lösung untersucht. Insbesondere wird dabei gezeigt, dass das Problem selbst auf Bäumen $\mathcal{NP}$-schwer bleibt. Zudem werden ganzzahlige lineare Programme zur Berechnung optimaler Partitionen entwickelt und diskutiert. Anschließend werden zwei Polynomialzeit-Algorithem basierend auf dem Greedy-Ansatz vorgestellt.

Datum: Mo, 7 Nov 2011, 13:00

Ort: SR 236

Vortragende(r): Alejandro Salinger, University of Waterloo

Inhalt: Paging for multi-core processors extends the classical paging problem to a setting in which several processes simultaneously share the cache. While cache eviction policies have been widely studied both in theory and practice for sequential processors, in the multi-core case the performance of even the most common eviction policies is not yet fully understood. In particular, there is almost no theoretical backing for the use of current eviction policies in multi-core processors. Recently, Hassidim proposed a model for multi-core paging, showing that LRU is not competitive against an offline policy that has the power to arbitrarily delay request sequences to its advantage. We propose a more realistic model in which requests must be served as they arrive. We study the problem of minimizing the number of faults, deriving bounds on the competitive ratios of natural strategies to manage the cache. We show that traditional online paging algorithms are not competitive in our model. We then study the offline paging problem and show that the problem of deciding if a request can be served such that at a given time each sequence has faulted at most a given number of times is NP-complete and that its optimization version is APX-hard (for an unbounded number of sequences). Lastly, we describe offline algorithms for the decision problem and for minimizing the total number of faults that run in polynomial time in the length of the sequences. This is joint work with Alejandro Lopez-Ortiz

Datum: Fr, 28 Okt 2011, 14:00

Ort: SR 301

Vortragende(r): Alex Lopez-Ortiz, University of Waterloo

Inhalt: In this talk we journey through three related subjects: 1) Paging algorithms. It has long been known that competitive analysis fails to reflect actual performance of paging algorithms in practice. We show that this can easily be fixed by a more careful definition of the denominator in the computation of the competitive ratio. The new measure, called parameterized analysis accurately predicts the performance of well known paging and list update algorithms. 2) Paging for multicore computers. We show that, surprisingly, this problem shares little with its sequential version and that good sequential algorithms exhibit rather bad performance in the multicore case. In particular we show that the offline optimum is NP-complete to compute, in contrast to the sequential case where the optimum is the well known Furthest-in-The-Future FTF algorithm (also known as LFD). 3) Multicore computing models. The widespread introduction of multicore computers marked the first time in fifty years in which the model of computation used by theoreticians (i.e. the RAM model) failed to reflect real life computers in which actual algorithms are run. This gap will only increase as the number of cores continues to grow. We then introduce a model of low degree parallelism which reflects modern multicore architectures while doing away with the main difficulties and drawbacks that plagued the PRAM model. We give a series of practical and theoretical arguments why this low degree assumption is critically important as well as realistic.

Datum: Di, 25 Okt 2011, 14:00

Ort: SR 301

Vortragende(r): Jan-Hinrich Kämper, Diplomarbeiter

Datum: Fr, 21 Okt 2011, 14:30

Ort: SR 301

Vortragende(r): Christian Staudt, Diplomarbeiter

Inhalt: Im Bereich Scientometrie ist die Analyse von Netzwerken, insbesondere Zitations- und Kollaborationsnetzwerken, zu einem wichtigen Werkzeug geworden. Kollaborationsnetzwerke sind auch Gegenstand dieser Arbeit: Auf Grundlage der Publikationsdatenbank DBLP werden die Beziehungen zwischen Publikationen und Autoren als Graphen modelliert. Standardtechniken der Analyse von (sozialen) Netzwerken (Zusammenhang, Gradverteilung, k-Core-Zerlegung) ergeben ein allgemeines Bild des Netzwerkes. Im Zentrum steht die Frage, ob und wie das Netzwerk von akademischen/sozialen Ereignissen geformt wird: Die Dagstuhl-Seminare haben das Ziel (kollaborative) Arbeit in innovativen Gebieten der Forschung zu fördern. Ihre Spuren in der Struktur des Netzwerkes werden mithilfe von Teilnehmerdaten untersucht. Außerdem liefert die Arbeit ein Beispiel für Modularity-Clustering auf einem empirischen Graphen, und behandelt die Frage, ob sich "kollaborative Cluster" aufgrund thematischer Ähnlichkeiten bilden. Schließlich wird untersucht, ob Eigenvektorzentralität im Kollaborationsgraphen geeignet ist, um fachlich einflussreiche Autoren zu identifizieren.

Datum: Fr, 21 Okt 2011, 14:00

Ort: SR 301

Vortragende(r): Gregor Stachowiak, Studienarbeiter

Datum: Mi, 19 Okt 2011, 17:30

Ort: Geb. 50.34, HS -101

Vortragende(r): Patrizio Angelini, Universita’ Roma Tre, Italy

Inhalt: Given k planar graphs G1,...,Gk, deciding whether they admit a simultaneous embedding with fixed edges (SEFE) and whether they admit a simultaneous geometric embedding (SGE) are NP-hard problems, for k >= 3 and for k >= 2, respectively. In this talk we consider the complexity of the SEFE problem and of the SGE problem when graphs G1,...,Gk have a fixed planar embedding. In sharp contrast with the NP-hardness of SEFE for three non- embedded graphs, we show that the SEFE problem is polynomial-time solvable for three graphs with a fixed planar embedding. Furthermore, we show that, given k planar embedded graphs G1,...,Gk, deciding whether a SEFE of G1,...,Gk exists and deciding whether a SGE of G1,...,Gk exists are NP-hard problems, for k >= 14 and k >= 13, respectively.

Datum: Mi, 19 Okt 2011, 11:30

Ort: SR 236

Vortragende(r): Patrick Flick, BA-Arbeiter

Inhalt: Ein Job ist malleable, wenn die von ihm benötigte Prozessorzahl nicht fix ist, und der Scheduler die Anzahl der dem Job zur Verfügung gestellten Prozessoren zur Laufzeit ändern kann. In einem System mit vielen fixed-size Jobs gibt es meist Prozessoren, die nicht zugeteilt werden können, ihre Anzahl schwankt jedoch. Diese Prozessoren mit einem malleable Job zu nutzen, kann die Effizienz des Systems ohne weitere Eingriffe erhöhen. Das Sortieren ist eine Basisfunktionalität, die von vielen Programmen benötigt wird und oft einen hohen Anteil am Rechenaufwand dieser Programme hat. In der vorgestellten Arbeit wurde ein malleable Sortierer implementiert, und mit dem Multiway Mergesort aus der MCSTL verglichen.

Datum: Fr, 14 Okt 2011, 14:00

Ort: SR 301

Vortragende(r): Thomas Bläsius, Diplomarbeiter

Inhalt: Ein PQ-Baum repräsentiert eine Menge von zyklische Ordnungen seiner Blätter, indem die Ordnung der Kanten um einen P-Knoten frei wählbar und um einen Q-Knoten bis auf Umkehrung festgelegt ist. Bei dem Problem {\sc Simultaneous PQ-Ordering} wird eine Menge von PQ-Bäumen betrachtet, deren Blätter zueinander in Beziehung stehen. Gesucht werden simultane Ordnungen für die Blätter aller PQ-Bäume, die sich mit den Beziehungen untereinander vertragen. Obwohl {\sc Simultaneous PQ-Ordering} im allgemeinen $\mathcal {NP}$-schwer ist, kann es für einfache Instanzen effizient gelöst werden. Dieses Ergebnis kann genutzt werden, um auf sehr einfache Weise das bedingte Einbettungsproblem {\sc Partially PQ-Constrained Planarity} für zweifach zusammenhängende Graphen und das Problem {\sc Simultaneous Embedding with Fixed Edges} für zweifach zusammenhängende Graphen mit zusammenhängendem Schnitt in Polynomialzeit zu lösen. Außerdem kann die Laufzeit des bisher schnellsten Algorithmus zum Erkennen von simultanen Intervallgraphen verbessert werden.

Datum: Fr, 9 Sep 2011, 14:00

Ort: SR 301

Vortragende(r): Thomas Gramer, Diplomarbeiter

Inhalt: Delay Management beschäftigt sich mit der Frage, ob es besser ist auf ein verspätetes Fahrzeug zu warten oder nicht. Ziel dabei ist es, die Gesamtverspätung aller im Transportnetz beförderten Passagiere zu minimieren. Bisherige Verfahren berechnen die bestmögliche Gesamtverspätung, skalieren aber nicht für große Transportnetzwerke. Im Vortrag werden Verfahren vorgestellt, welche die Gesamtverspätung basierend auf lokaler Suche berechnen. Ziel dabei ist eine Beschleunigung der Berechnung gegenüber bestehenden ILP basierten Verfahren. Nicht optimale Lösungen werden somit zwar in Kauf genommen, lokale Suchverfahren scheinen aber dennoch geeignet zu sein, sehr nahe an die ILP basierten Lösungen heranzukommen.

Datum: Fr, 2 Sep 2011, 14:30

Ort: SR 301

Vortragende(r): David Lisowski, Diplomarbeiter

Datum: Fr, 2 Sep 2011, 14:00

Ort: SR 301

Vortragende(r): Florian Merz, Studienarbeiter

Inhalt: Graphpartitionierung ist das Problem, die Knotenmenge eines Graphen in disjunkte, gleich große Teilmengen aufzuteilen, welche die Anzahl der Kanten zwischen diesen Teilmengen minimiert. In dieser Arbeit beschreiben wir einen Algorithmus, um große Zufallsgraphen generieren, zu denen wir eine optimale Partitionierung kennen. Um dies zu erreichen, generieren wir zuerst dichte Teilgraphen, für welche wir die untere Schranke für die Größe deren minimalen Schnittes kennen. Diese Teilgraphen verbinden wir danach mit einigen wenigen Kanten, so dass die durch die Teilgraphen induzierte Partitionierung optimal ist.

Datum: Fr, 26 Aug 2011, 14:00

Ort: SR 301

Vortragende(r): Roland Kluge, Bachelorarbeiter

Inhalt: Um dynamische Cluster-Algorithmen evaluieren zu können, benötigt man Testdaten, die idealerweise aus der wirklichen Welt stammen. Leider sind große Testinstanzen selten und stehen zudem meist auch nicht frei zur Verfügung, was es schwierig macht, unterschiedliche Algorithmen oder deren Implementierungen auf einer gemeinsamen Testdatenbasis zu vergleichen. Diese Bachelorarbeit beschäftigt sich mit dem Entwurf und der Umsetzung eines effizienten Generators, der in der Lage ist, große Netzwerke sowie deren Entwicklung über zahlreiche Zeitschritten hinweg zu erzeugen.

Datum: Mi, 24 Aug 2011, 14:00

Ort: SR 236

Vortragende(r): Jan Wassenberg

Inhalt: This talk will describe three techniques for speeding up integer sorting that result in the fastest currently known algorithm for shared-memory machines. Counting sort first determines the frequency of each key value, and then distributes successive items to the appropriate bins. We propose using virtual memory hardware as an `oracle' to designate the write position without requiring an initial scan over all items. Writing directly to a multitude of bins is inefficient on current and probably also future computer architectures. We describe the problem and show how to avoid it with write-combining. This technique is also applicable to other algorithms with frequent memory accesses. Write-combined virtual-memory counting sort is limited to small (e.g. 8-bit) keys. We show how to extend it to 32 or more bits and associate keys with an optional payload. A special ordering of the radix sorting passes improves locality on NUMA machines. The combination of these techniques results in software that outperforms a Fermi GPU when data-transfer overhead is included. Our implementation also outperforms Intel's radix sort by a factor of 1.64.

Datum: Fr, 1 Jul 2011, 14:00

Ort: SR 301

Vortragende(r): Raoul Steffen, Studienarbeiter ITI Sanders

Inhalt: Naive implementations of external matrix multiplication will cause O(n^4) I/Os, where n is the side length of the matrices. I explain how to reduce the number of I/Os to O(n^3) with the side effect of simplifying transposition, too. Employing the Strassen-Algorithm, I try to further reduce I/Os and computation. Theoretical I/O-counts rsp. I/O-bounds including comparison of constant factors and test results are discussed for some algorithms.

Datum: Mi, 29 Jun 2011, 14:00

Ort: SR 236

Vortragende(r): Maarten Löffler, University of California Irvine

Inhalt: We show that Delaunay triangulations and compressed quadtrees are equivalent structures. More precisely, we give two algorithms: the first computes a compressed quadtree for a planar point set, given the Delaunay triangulation; the second finds the Delaunay triangulation, given a compressed quadtree. Both algorithms run in deterministic linear time on a pointer machine. Our work builds on and extends previous results by Krznaric and Levcopolous and Buchin and Mulzer. Our main tool for the second algorithm is the well-separated pair decomposition (WSPD), a structure that has been used previously to find Euclidean minimum spanning trees in higher dimensions. We show that knowing the WSPD (and a quadtree) suffices to compute a planar EMST in linear time. With the EMST at hand, we can find the Delaunay triangulation in linear time. As a corollary, we obtain deterministic versions of many previous algorithms related to Delaunay triangulations, such as splitting planar Delaunay triangulations, preprocessing imprecise points for faster Delaunay computation, and transdichotomous Delaunay triangulations.

Datum: Mi, 22 Jun 2011, 14:00

Ort: SR 236

Vortragende(r): Prof. Paul Waddell, Berkeley

Inhalt: This talk will describe a research project to integrate behavioral microsimulation of urban development and location of households, firms and real estate development, with procedural geometric modeling of urban landscapes including local streets, parcels, and buildings. By implementing an open source platform, called UrbanVision, to tightly couple approaches drawn from quite different domains, we strive to achieve novel means of modeling and analyzing the spatial structure and behavioral patterns within urban regions. Coupling this platform with microsimulation modeling of traffic is a research direction for the current project, but existing microsimulation traffic models generally lack sufficient computational performance for this tight integration to be very productive for operational use on large scale urban regions or even larger regions. The motivation for this work is to allow planners and the public to engage in planning efforts to reduce greenhouse gas emissions by reducing vehicle miles travelled. A policy strategy for this is, as adopted in state laws in California, is to reduce the need to drive by making walk and transit relatively more attractive modes, using a combination of land use and transportation policies.

Datum: Do, 12 Mai 2011, 11:30

Ort: SR -118

Vortragende(r): Jochen Seidel, Diplomarbeiter

Inhalt: In systems with Non-Uniform Memory Access (NUMA), memory bandwidth depends upon the memory location relative to the accessing processor. Each processing node can have its own local memory, but accesses foreign memory transparently in the same address space. Our approach is to minimize memory access time by scheduling jobs on the processing node where most memory access happens. We have implemented a working user-land scheduler favoring local memory access with a user interface similar to the one of Intel Thread Building Blocks (TBB). Furthermore, we devise a model to predict the effects of concurrently running jobs. We then show theoretically and in experiments, how efficiency can be gained by executing two di?erent jobs in parallel rather than sequentially. This implies the concurrent execution of more than one query in a DBMS can be advantageous.

Datum: Mi, 11 Mai 2011, 11:30

Ort: SR 236

Vortragende(r): Jochen Speck

Inhalt: We give a fast algorithm for scheduling n tasks with flexible amount of parallelism on m processors, provided the speedup functions of the tasks are concave. We give efficient parallelizations of the algorithm that run in polylogarithmic time. Previous algorithms were sequential and required quadratic work. This is in some sense a best-possible result since the problem is NP-hard for more general speedup functions.

Datum: Mi, 20 Apr 2011, 14:00

Ort: SR 131

Vortragende(r): Christof Doll, Studienarbeiter

Inhalt: Im Gegensatz zu vielen gängigen Clusterungsverfahren bietet schnittbasiertes Clustern die Möglichkeit, insbesondere für die Dichte innerhalb der Cluster eine untere Schranke anzugeben und damit eine bestimmte Qualität zu garantieren. Flake et al. entwickelten einen (statischen) hierarchischen schnittbasierten Ansatz, der Clusterungen verschiedener Granularität bezüglich des zugrundeliegenden Graphen erzeugt. Jede dieser Clusterungen bietet eine schnittbasierte Qualitätsgarantie. Diese Arbeit überträgt den hierarchischen Ansatz von Flake et al. in ein dynamisches Szenario, das Veränderungen der Kantengewichte im zugrundeliegenden Graphen zulässt. Der entwickelte dynamische Algorithmus erlaubt nach einer Veränderung (Gewichtserhöhung oder -reduktion) eine effiziente Neuberechnung der Clusterungshierarchie unter Beibehaltung der Qualitätsgarantie.