Next Seminars

Research Seminar

Fall 2018

Route Planning with Temporary Road Closures

  • Date: Fri, 21 Dec 2018, 14:00
  • Location: SR 301
  • Speaker: Christian Bräuer, ITI Wagner; Masters Thesis
  • Inhalt: We study the problem of route planning with temporary road-closures. In practice, road segments, e.g. in residential or downtown areas, are closed at certain times. In addition, in many countries general weekend and night driving bans apply. Mainly trucks are affected by these driving bans. The road-closures may inflict waiting time along a route for which parking lots are needed. Routes with mathematical earliest arrival at the destination may contain loops and other detours. In this thesis we define a model which yields reasonable routes in practice, where the road-closures are taken into account. We distinguish between the travel time and the driving time of a route. The travel time is the time span between the start and the end of the route. The driving time is the duration in which the driver moves his vehicle. The distinction between travel time and driving time may yield multiple routes per route planning query. Thus, we use the concept of Pareto-optimality. We present an algorithm which calculates Pareto-optimal routes according to the model and adapt known speed up techniques to the algorithm. Using heuristic algorithms, we achieve a running time per query of a few seconds.

Dynamische Baumkompression mit Top Trees

  • Date: Wed, 19 Dec 2018, 13:30
  • Location: To appear.
  • Speaker: Jan Ellmers, ITI Sanders; Bachelors Thesis
  • Inhalt: In dieser Arbeit sehen wir uns Verbesserungsmöglichkeiten für Tree Compression mit Top Trees an. Wir entwickeln zwei neue Navigationsfunktionen, die ebenfalls in logarithmischer Zeit laufen und keine zusätzlichen Informationen benötigen, und zeigen, wie die Navigation von Hübschle-Schneider and Raman mit logarithmischem Platz realisiert werden kann. Des Weiteren zeigen wir, wie wir weniger Information für den Top Tree speichern müssen, und stellen neue Regeln für das Erstellen des Top Trees vor, die bessere Kompressionsraten und Laufzeiten haben. Zudem untersuchen wir die Möglichkeit, an einem komprimierten Baum Änderungen vorzunehmen. Wir testen unsere Ergebnisse an dem XML Corpus von Hübschle-Schneider and Raman und schauen uns an diesem die praktischen Auswirkungen von Slowing Down an.

Optimierung globaler Flexibilität von elektrischen Lasten mittels Genetischer Algorithmen

  • Date: Fri, 14 Dec 2018, 14:30
  • Location: SR 301
  • Speaker: Johanna Rey, ITI Wagner; Bachelors Thesis
  • Inhalt: Lösungsansätze um mit Demand Side Management auf Veränderungen durch die Energiewende zu reagieren sind größtenteils auf private Haushalte fokusiert. Dies führt dazu, dass in der Industrie Demand Side Management kaum eingesetzt wird. Durch größere Mengen an elektrischen Lasten die in der Industrie verwendet werden, liegt jedoch gerade dort ein großes Potential in der Anwendung liegt. Wir entwickeln einen Genetischen Algorithmus, der mit dem von Barth et al. entwickelten neuen Scheduling-Ansatz berechnet was mit unterschiedlichen Graden an Flexibilität erreicht werden kann. Relativ zu den durch ein MIP-Solving errechneten Werten erreichen wir mit unserem Algortihmus Ergebnisse, die innerhalb von vier Sekunden Werte mit im Schnitt 95% der Qualität aufweisen können.

A Flow-Based Initial Partitioning Algorithm for Multilevel Graph Partitioning

  • Date: Fri, 14 Dec 2018, 14:00
  • Location: SR 301
  • Speaker: Tim Niklas Uhl, ITI Wagner; Bachelors Thesis
  • Inhalt: The graph partitioning problem is to partition the nodes of a graph into k blocks of roughly equal size such that the number of edges running between blocks is minimized. Most state-of-the-art graph partitioning algorithms are based on the multilevel scheme which obtains a partition of a graph by recursively contracting the input graph, initially partitioning the contracted graph and refining the partition while undoing the contraction. While flow-based approaches have been used for partition refinement, flow-based initial partitioning has not received any attention. In this thesis we investigate a flow-based initial partitioning algorithm. We incorporated node and edge weight into the bipartitioning algorithm FlowCutter. FlowCutter computes a sequence of s-t-cuts of increasing balance using incremental flow augmentations. We evaluate the performance of the adapted algorithm by replacing the initial partitioner in the multilevel graph partitioner KaHiP. We show that our algorithm yields better initial partitions than KaHiP when contraction is stopped earlier and is also able to improve the final cut size. On 16 out of 30 graphs from the Walshaw Benchmark set we find cuts with the same size as KaHiP, while we achieve an improvement on 5 graphs. We further show that coarsening based on the Louvain method is able to improve cut capacities of the initial partition. Using our algorithm for initial partitioning we find better initial partitions than KaHiP for 24 out of 30 graphs even when KaHiP stops contraction early and the resulting graphs are therefore larger than those obtained using Louvain.

Distributed Kernelization for Independent Sets

  • Date: Tue, 11 Dec 2018, 13:00
  • Location: SR 301
  • Speaker: Tom George, ITI Sanders; Bachelors Thesis
  • Inhalt: To appear.

A Practical Analysis of Kernelization Techniques for the Maximum Cut Problem

  • Date: Fri, 30 Nov 2018, 13:00
  • Location: SR 236
  • Speaker: Damir Ferizovic, ITI Sanders; Masters Thesis
  • Inhalt: In this work we study existing and new kernelization techniques for a famous NP-Complete problem: extsc{Max-Cut}. Primarily the unweighted case is being studied, but also the signed and weighted versions are addressed to some degree. While the unweighted extsc{Max-Cut} problem is not ubiquitous in practice, the signed and weighted version are. Furthermore, the achieved results from the unweighted case do set a lower bound for the expectations to be had on the more general cases. At the beginning we provide a broad overview of existing techniques and the fixed-parameter tractable algorithms they imply. We then introduce any new set of rules that have been created within our work and analyze the used reduction rules from previous works. Moreover, we outline our approach on how we integrated the reductions into our testing suite. For some set of rules a proof is also given if they are a subset of another one; making that other rule be able to do everything it can do, and more. Thus, this allows us to ignore such rules from further regard. Within the closure of our work, a practical analysis is given: The usefulness of each reduction rule is scrutinized and the results of testing a wide range of graphs is provided. We also specifically analyze the practical results implied by the work from Etscheid and Mnich cite{crowston2014satisfying}, which guarantee a linear sized kernel. As utilized in their work, we also deploy related techniques  to compute a polynomial-time solvable subgraph for further reduction of the kernel size.

Approximate Transit Node Routing - An Approximate Distance Oracle for Social Networks

  • Date: Tue, 27 Nov 2018, 14:00
  • Location: SR 211
  • Speaker: Katharina Flügel, ITI Sanders; Bachelors Thesis
  • Inhalt: Computing shortest paths is a fundamental graph problem with many real-life applications. Naive methods such as Dijkstra's algorithm are not fast enough for today's graphs with millions of vertices and edges. We present approximate transit node routing (aTNR), an approximate distance oracle for social networks with a limited additive error. It is an extension to the transit node routing framework which was originally developed for road networks. Distances can be computed significantly faster with aTNR compared to the naive approaches. We can adjust the maximum error for each graph and even compute exact distances at the cost of a longer preprocessing time. The distance between two vertices is computed using a three-hop via the transit nodes, a small set of central vertices. For each vertex, a set of access nodes is chosen from the transit nodes via which the three-hop is computed for that vertex. We evaluate aTNR on multiple different graphs regarding the preprocessing time, preprocessing size, query time, and approximation error. Smaller graphs are preprocessed in mere seconds, and even graphs with more than one hundred million edges can be preprocessed in less than two minutes. Most queries take about 20 microseconds and cause only a very small approximation error. Our distance oracle is particularly proficient in terms of space consumption as it requires less than 50 bytes per vertex. In addition to aTNR, we define the Voronoi search distance oracle, a variation of aTNR which increases the approximate error in exchange for potentially faster preprocessing and queries.
  • Date: Fri, 23 Nov 2018, 14:00
  • Location: SR 301
  • Speaker: Kai Fieger, ITI Sanders; Masters Thesis
  • Inhalt: This thesis presents a parallel algorithm that solves the longest path problem for weighted undirected graphs. The algorithm uses dynamic programming and graph partitioning in order to find the longest path between two vertices. The algorithm finds the optimal longest path and not an approximation of it like many other approaches for NP-complete problems. We first present the serial algorithm and then how it can be parallelized. Through experiments we measured the speedup of the parallel algorithm compared to its serial counterpart. We achieved reasonable speedups. We also demonstrate that the algorithm has possible applications in solving the Hamiltonian cycle problem.

A Block-Cut-Tree-based Switching Algorithm for Cacti

  • Date: Tue, 20 Nov 2018, 14:00
  • Location: SR 301
  • Speaker: Florian Krüger, ITI Wagner; Bachelors Thesis
  • Inhalt: The Maximum Transmission Switching Flow Problem (MTSF) focuses on maximizing the power flow within an electrical power grid by allowing transmission lines to be removed from the grid, where the latter procedure is referred to as switching. MTSF is an optimization problem and known to be NP-complete, even on strongly restricted graph classes such as cacti. Therefore the standard approach is to solve an instance of its formulation as a Mixed Integer Linear Program (MILP). In this thesis, we present an algorithm of exponential complexity to solve MTSF for unbounded cacti grids to optimality by utilizing the structure of its Block-Cut-tree. We achieve this by solving a power flow model for subgraphs and then composing partial solutions to an overall solution. We furthermore introduce a heuristic to gain improvements in terms of running time. In conclusion we evaluate the results of our algorithm in comparison to solving the MILP on real power grid instances, that have been modified to represent cacti. We identify the cause for the exponential running time and also assess the solution deviation from optimality of the heuristic.

PoI Anfragen im Vergleich

  • Date: Tue, 20 Nov 2018, 13:30
  • Location: SR 301
  • Speaker: Hamidulah Doust, ITI Wagner; Bachelors Thesis
  • Inhalt: Fast täglich benutzt man einen Navigator um den schnellsten Weg von einem Startpunkt zu einem Zielpunkt zu berechnen. Dabei existieren Anfragen, die generell öfters verwendet werden. Beispielsweise Interessiert man sich für die Haltestellen des öffentlichen Verkehrs oder die nächste Ladestation für Elektrofahrzeuge. Um diese Art von Anfrage zu lösen benutzt man kürzeste Wege Algorithmen. Speziell interessant in dieser Arbeit ist das "One to Many" Problem, sprich von einem Startpunkt die kürzesten Wege zu einer Menge von Zielpunkten zu bestimmen. Im Laufe dieser Bachelorarbeit vergleichen wir unterschiedliche "One to Many" Algorithmen. Ebenfalls werden neue "One to Many" Algorithmen vorgestellt. Wir testen und evaluieren diese Algorithmen auf verschiedene Datensätzen, u.a. auf Haltestellen des öffentlichen Verkehrs als auch Ladestationen für Elektrofahrzeuge.

Dijkstra-basiertes Mapmatching

  • Date: Tue, 20 Nov 2018, 13:00
  • Location: SR 301
  • Speaker: Peter Maucher, ITI Wagner; Bachelors Thesis
  • Inhalt: In dieser Arbeit beschreiben wir einen neuen Ansatz zur Lösung des Mapmatching-Problems basierend auf Dijkstras Algorithmus. Zu einem sich in einem Straßennetz- werk bewegenden Objekt werden Positionsmessdaten aufgezeichnet. Im Mapmatching-Problem wird zu diesen Messdaten ein möglichst plausibler Pfad in dem Graphen gesucht, der das Straßennetzwerk repräsentiert. Dijkstras Algorithmus löst das kürzeste-Wege-Problem effizient. Unser Ansatz erweitert diesen Algorithmus, indem die Kantengewichte abhängig von den gemessenen Daten verringert werden. Mit den geänderten Kantengewichten entsteht eine Lösung des Mapmatching-Problems. Zur Anpassung der Gewichte werden Wegintegrale über die Graphkante verwendet. Wir zeigen die Effizienz unseres Algorithmus auf echten Daten, indem wir ihn mit einem unmodifizierten Dijkstra vergleichen. Die Genauigkeit wird durch den Vergleich mit einem Standardalgorithmus für Mapmatching mit Namen ST-Matching gezeigt.
  • Date: Mon, 12 Nov 2018, 14:00
  • Location: SR 236
  • Speaker: Guangping Li, ITI Sanders; Masters Thesis
  • Inhalt: Stochastic local search (SLS) is an elementary technique for solving combinational problems. In the first section of this paper, we introduce an efficient SLS heuristic solver for Boolean Satisfiability Problem (SAT), in which the decisions only based on the probability distribution. We experimentally evaluate and analyze the performance of our solver in a combination of different techniques, including simulated annealing and walkSAT. With formula partition, we introduce a parallel version of our solver in the second section. The parallelism improves the efficiency of the solver. Using different random generator in solving the sub-formula can bring further improvement in performance to our parallel solver.

Kernelization for Maximum Weight Independent Sets and Distributed Connected Components

  • Date: Fri, 9 Nov 2018, 14:00
  • Location: SR 301
  • Speaker: Sebastian Lamm, ITI Sanders - Research Overview
  • Inhalt: After spending half a year at the TAA research group in Vienna, I would like to present an overview of the work I did during my stay. The talk will most likely be split into two parts. First, I will talk about our recent results on kernelization for the maximum weight independent set problem. In particular, I will present a set of novel reduction rules that are able to significantly reduce the size of large real-world graphs. This allows us to compose an efficient branch-and-reduce algorithm that outperforms the current state-of-the-art. Second, we will take a look at distributed algorithms for finding connected components. My work here focuses on achieving scalability by focusing on communication efficieny. For this purpose, I developed and engineered an algorithm that uses various types of local contraction routines. In addition to providing state-of-the-art performance, the optimizations deployed can be used to significantly speedup existing approaches.

Parallelization Techniques for Customizable Contraction Hierarchies

  • Date: Fri, 2 Nov 2018, 13:30
  • Location: SR 301
  • Speaker: Max Göttlicher, ITI Wagner; Bachelors Thesis
  • Inhalt: Mit Customizable Contraction Hierarchies können sehr schnelle Routenabfragen realisiert werden, wie sie für die Echtzeitvorschau in einigen Onlinediensten benötigt werden. Darüber hinaus können auch aktuelle Verkehrsdaten verwendet werden, um eine realistische Fahrzeit zu erhalten. Ermöglicht wird dies durch eine zweiphasige Vorberechnung, die zunächst eine metrikunabhängige Graphstruktur berechnet, die erst in der zweiten Phase um eine Metrik erweitert wird. Die zweite Phase bietet eine guten Ansatzpuntk für weitergehende Optimierungen, da sie im Vergleich zur ersten Phase relativ oft ausgeführt werden muss und eine lange Vorberechnungszeit die Verwendung aktueller Verkehrsdaten verhindern würde. Durch Parallelisierung kann die Laufzeit stark reduziert werden. Zusätzliche Beschleunigung kann durch verschiedene sequentielle Optimierungen erreicht werden, die auch bei einer parallelen Ausführung noch zum Tragen kommen.

Effizienter Umlegungsalgorithmus für den öffentlichen Verkehr mit Fahrzeugkapazitäten

  • Date: Fri, 2 Nov 2018, 13:00
  • Location: SR 301
  • Speaker: Robin Berger, ITI Wagner; Bachelors Thesis
  • Inhalt: Ein wichtiges Problem bei der Verkehrsplanung im öffentlichen Verkehr ist es, für einen gegebenen Fahrplan und eine gegebene Nachfrage zu wissen, wie viele Personen welches Fahrzeug verwenden. In dieser Arbeit wird ein Verfahren vorgestellt, das dieses Problem löst. Hierbei werden auch Fahrzeugkapazitäten und die Tatsache betrachtet, dass Fahrgäste versuchen überfüllte Fahrzeuge zu meiden.

Relaxed Priority Queues: Using buffers to guarantee quality

  • Date: Wed, 31 Oct 2018, 11:30
  • Location: SR 236
  • Speaker: Holger Ebhart, ITI Sanders; Masters Thesis
  • Inhalt: In this work we present a new approach for a concurrent relaxed priority queue design. Due to popularity of multi-core systems we see a need to adopt basic data structure to these systems for further performance increase. We present the buffered multi queue, a priority queue adopted for concurrent access. The buffered multi queue supports fast insertions into per-thread local priority queues and still guarantees a low rank error for removals. To hold guarantees we propose an output buffer where small elements were moved into. Elements were only popped from this buffer. By adjusting the capacity of the output buffer, we have a trade-off between high throughput rates and good quality. Relaxation of the queue is introduced via the buffer and allows us to return only one of the smallest elements. For this behavior we use a more relaxed semantic than for sequential priority queues, as such a semantic becomes necessary when accessing a priority queue concurrently. We prove that the maximal rank error is in O(buffer_size) as well as the maximal starvation. The starvation is a newly introduced quality metric, stating the time a queued element is skipped for output. Within experiments with different workloads and against competitors we show that our approach keeps up with others in performance. But in quality of returned elements we outperform all other approaches.

Local Page Numbers

  • Date: Fri, 12 Oct 2018, 14:30
  • Location: SR 148
  • Speaker: Laura Merker, ITI Wagner; Bachelors Thesis
  • Inhalt: Ein Buch besteht aus Halbebenen, sogenannten Seiten, die eine gemeinsame Gerade haben, auch Spine genannt. Ein Graph wird in ein Buch eingebettet, indem die Knoten auf dem Spine angeordnet werden und jede Kante auf genau einer Seite eingebettet wird, wobei sich Kanten auf der gleichen Seite nicht kreuzen dürfen. Eine Bucheinbettung heißt k-lokal, wenn an jedem Knoten maximal k Seiten beteiligt sind. Die (global) Page Number ist die Mindestanzahl an Seiten, die für eine Bucheinbettung benötigt wird, während die local Page Number das kleinste k ist, für das es eine k-lokale Bucheinbettung gibt. Wir finden Schranken für die local Page Number einiger Graphklassen wie vollständige Graphen, planare Graphen und k-Bäume. Im Anschluss betrachten wir das NP-schwere Problem, eine k-lokale Bucheinbettung für einen gegebenen Graphen mit fester Knotenreihenfolge zu finden.

Top Trumps - The Graph-Theoretical Properties of a Children's Game

  • Date: Fri, 12 Oct 2018, 14:00
  • Location: SR 148
  • Speaker: Lasse Wulf, ITI Wagner; Masters Thesis
  • Inhalt: The game "Top Trumps" is a simple card game played between two players. Each Top Trumps deck has a certain theme to it, say for example the theme "sports cars". Then, on each card, there is a picture of a certain sports car and a set of categories describing the car, e.g. "top speed", "engine power", "engine displacement" and "weight". One player begins and chooses one of the categories, the players compare the values of the top two cards of their decks in the chosen category. The winner shuffles the two cards to the bottom of his or her deck and is choosing player for the next round. Although the game is quite simple and has never been investigated scientifically, the surrounding theory is surprisingly elegant and non-trivial, especially from a graph-theoretical point of view. In this talk, we are concerned with optimal play, fairness of the game, and first-player-advantage. We also see that the topic is strongly connected to the concept of the width of a partially ordered set. In particular, we show a generalization of the well-known Dilworth's theorem in terms of "Top Trumps deck realizations".

Verkabelung von Windfarmen auf Bäumen

  • Date: Fri, 5 Oct 2018, 14:00
  • Location: SR 236
  • Speaker: Dominik Stampa, ITI Wagner; Bachelors Thesis
  • Inhalt: The wind farm cabling problem deals with installing cables between wind turbines and substations of a wind farm in order to conduct electric power from turbines to substations. For this task several types of cables are given and the cheapest cable installation is to be found. In the model, turbines and substations are represented by vertices of a graph. Cables can only be placed at the edges of this graph. Whereas this problem is NP-hard on general graphs, in this thesis the wind farm cabling problem is considered on tree graphs only. We describe different variants of the problem with the help of several parameters and analyse their complexity. Amongst others, a polynomial-time algorithm for the wind farm cabling problem on path graphs, where the produced power of a wind turbine has to be conducted to exactly one substation, is given. On trees the cabling problem is already NP-hard if an arbitrary set of cable types is given - no matter how the values of other parameters are chosen.

Spring 2018

Wind Farm Cabling using Spectral Clustering

  • Date: Tue, 18 Sep 2018, 14:30
  • Location: SR 301
  • Speaker: Niklas Fuhrberg, ITI Wagner; Bachelors Thesis

Drawing a Level Planar Graph with Fixed Slopes

  • Date: Tue, 18 Sep 2018, 14:00
  • Location: SR 301
  • Speaker: Nadine Krisam, ITI Wagner; Bachelors Thesis
  • Inhalt: In this thesis we study level planar drawings with two fixed slopes of the edges (LP2-drawings). We present an algorithm that, given a level planar graph, decides whether it has an LP2-drawing with an additional requirement of rectangular inner faces. After that, we drop the requirement of rectangular inner faces and provide an algorithm that decides whether a general LP2-drawing exists. Both algorithms have polynomial running time. In the conclusion, we give an outlook how to extend the latter algorithm to work on multiple fixed slopes.

Parallel Greedy Graph Matching

  • Date: Thu, 6 Sep 2018, 14:00
  • Location: SR 301
  • Speaker: Fredrik Manne, ITI Sanders; Guest from the University of Bergen, Norway (Department of Informatics)
  • Inhalt: The weighted matching problem has numerous applications in scientific computing. Although there exists efficient polynomial time algorithms for the problem, in practise these are often too slow for large problems. It is therefore of interest to study fast approximation algorithms. In this presentation we will look at an approximation algorithm called the Suitor algorithm that computes the same solution as the greedy approach, but does so without sorting, and that is also higly amendable to parallelization. From this algorithm we branch out in various directions to investigate how it can be applied to different matching problems. Fredrik Manne is a professor at the University of Bergen and is currently on sabatical leave at KIT. His main interests are in combinatorial scientific computing and in particular in designing and implementing parallel algorithms.

Hierarchical Task Network Planning using SAT Techniques

  • Date: Tue, 24 Jul 2018, 13:00
  • Location: SR 301
  • Speaker: Dominik Schreiber, ITI Sanders; Masters Thesis
  • Inhalt: Automated planning is useful for a wide range of general decision-making processes in the area of Artificial Intelligence. The solving approach of encoding a planning problem into propositional logic and finding a solution with a SAT solver is a well established method. Likewise, a planning model called Hierarchical Task Networks (HTN) which enhances planning problems with expert knowledge can help to find structured plans more easily and efficiently. This work focuses on combining these techniques by using SAT solving techniques to resolve HTN planning problems. Initially, a previous approach to encode HTN problems in SAT by (Mali and Kambhampati, 1998) is analyzed, and various shortcomings are identified from today's perspective. Then, three original encodings are proposed: Grammar Constrained Tasks (GCT) which is inspired by one of the previous encodings and is the first to feature modern HTN domains and recursive task relationships; Stack Machine Simulation (SMS) which is designed for incremental SAT solving and works reliably on all special cases; and Tree-like Reduction Exploration (T-REX), which leads to a particularly efficient solving process due to its short amount of needed iterations and various introduced optimizations. All encodings are implemented to exploit existing HTN grounding routines, and the T-REX approach features a novel abstract formula notation and an efficient Interpreter application tailored to the encoding. In addition, an Anytime plan length optimization within T-REX is proposed. Experiments show that SMS dominates GCT, and T-REX dominates SMS. The proposed T-REX planning framework outperforms a state-of-the-art classical SAT planner on various domains. Regarding run times, T-REX cannot compete with state-of-the-art HTN planners yet, but is still an appealing planning approach due to its robustness, its plan length optimization, and its proving abilities. By the design, implementation and evaluation of T-REX, the work at hand demonstrates that HTN planning via SAT Solving is a viable option and worthy of the attention of future research.

Support Vector Machines via Multilevel Label Propagation

  • Date: Wed, 11 Jul 2018, 13:00
  • Location: SR 301
  • Speaker: Matthias Schmitt, ITI Sanders; Bachelors Thesis
  • Inhalt: The time complexity of support vector machines (SVM) prohibits training on huge data sets with millions of samples. Multilevel SVMs were developed to allow for time efficient training on huge data sets. In this thesis we present a new faster multilevel support vector machine framework which utilizes the near-linear time label propagation algorithm for the construction of the problem hierarchy. While regular SVM perform the entire training in one - time consuming - optimization step, multilevel SVMs first build a hierarchy of problems decreasing in size that resemble the original problem and then train an SVM model for each hierarchy level benefiting from the solved models of previous levels. Our experiments on a large number of benchmark data sets show that our framework (KaMLSVM), when compared to the previous best multilevel SVM, achieves a speed-up of more that two on almost all data stet and up to 20 on large data sets with many features.

"Quadratic"-work construction of terabyte-scale text indexes

  • Date: Wed, 4 Jul 2018, 13:00
  • Location: SR 301
  • Speaker: Juha Kärkkäinen, ITI Sanders; Guest from the University of Helsinki (Department of Computer Science)
  • Inhalt: Suffix array and LCP array are fundamental data structures underlying many modern text indexes, and their construction is often a main bottleneck in index construction. In this talk, we review some recent practical external memory algorithms for constructing these data structures even for terabyte-scale texts. The algorithms share a common approach that results in work and I/O complexities involving the term n^2/M, where n and M are the sizes of the input and the main memory, respectively. Such quadratic complexities are easy to dismiss as unscalable but we show experimental results and theoretical arguments supporting the practicality of this approach.

Partial Contraction Hierarchies

  • Date: Fri, 22 Jun 2018, 14:30
  • Location: SR 301
  • Speaker: Jonas Meier, ITI Wagner; Bachelors Thesis
  • Inhalt: In großen oder komplexen Straßengraphen können Kürzeste-Wege-Anfragen mit naivem Dijkstra-Algorithmus sehr schnell sehr langsam werden. Eine populäre Beschleunigungstechnik für das Finden von Kürzesten Wegen ist die sogenannte Contraction Hierarchy, welche iterativ Knoten kontrahiert durch Entfernen dieser und anschließendem Einfügen von shortcuts in den Graphen. Wenn die Berechnung einer kompletten contraction hierarchy nicht möglich oder zu aufwendig ist, kann man den Graphen auch nur teilweise kontrahieren. In dieser Arbeit untersuchen wir die Leistung von Partial Contraction Hierarchies. Wir evaluieren Möglichkeiten, den Tradeoff von Speicherplatz und Beschleunigung bei contraction hierarchies zu verändern. Dies versuchen wir einerseits dadurch, Knoten unkontrahiert zu lassen und andererseits durch Entfernen von shortcuts aus dem Graph. Diesen Kompromiss haben wir systematisch untersucht und herausgefunden, dass man in einer contraction hierarchy fast nichts weglassen kann, ohne gleich viel Laufzeit zu verlieren.

Transmission Network Expansion Planning using the Railway Network

  • Date: Fri, 22 Jun 2018, 14:00
  • Location: SR 301
  • Speaker: Chao Wang, ITI Wagner; Masters Thesis
  • Inhalt: The main goal of Transmission Network Expansion Planning (TNEP) is to determine optimal investments on transmission line additions from the candidate network to satisfy reliability criteria under future load and generation scenarios. Up to now, most of the current researches focus on using different methods to find optimal solution of TNEP problem, however, how to generate the candidate network, where the new lines can be installed, has also drawn our attentions. Hence, this thesis explores a new design problem about using railway network to expand the power grid, which is defined as follows. Given the current power grid and the railway network, we build connections between both network and find, where and how many new lines along new connections and railway edges should be added with an object of minimizing the cost of lines construction under the electrical constraints. In order to build connections between the power grid and railway network, the algorithm KD-tree is proposed in our work, which can efficiently find k-nearest neighbors in railway network for each node in the power grid. For finding an optimal solution of TNEP problem, we have adopted mathematical models, such as mixed-integer non-linear model, binary linear model and mixed-integer linear model, which are been discussed in the most researches. Additionally, we have also proposed a heuristic algorithm and compared with the mathematical model. The heuristic algorithm performs more computational efficiency than the mathematical model. In the end, a simple case study of 8-buses system is used to illustrate the non-linear and linear mathematical model. Furthermore, the realistic scenarios of German including the power grid and the railway network is implemented and tested by using the linear mathematical model and the heuristic algorithm. The non-linear mathematic model comparing to the linear model is easy to understand, but has lower computational efficiency and less optimal result. On the other hand, the heuristic model shows the highest efficiency but the result is way below the ones from linear mathematic model.

Parallelizing Graphplan

  • Date: Wed, 30 May 2018, 13:00
  • Location: SR 301
  • Speaker: Patrick Hegemann, ITI Sanders; Bachelors Thesis
  • Inhalt: Automated Planning is a method used in artificial intelligence systems such as autonomous robots or automatic satellite control. While there already are some planning algorithms that make use of multi-core processors, this thesis proposes a parallelized version of the Graphplan algorithm. The proposed algorithm works by transforming plan extraction problems for different horizon lengths into the Boolean Satisfiability Problem (SAT) and solving multiple SAT formulas in parallel. Experiments based on the problem instances provided by the 2014 International Planning Competition show that this method results in a significant parallel speedup and is able to outperform the state-of-the-art SAT-based sequential planner Madagascar in some problem domains. A disadvantage of the proposed algorithm is high memory consumption for some problems with certain configurations.

Faster Public Transit Routing with Unrestricted Walking

  • Date: Wed, 23 May 2018, 13:00
  • Location: SR 301
  • Speaker: Jonas Sauer, ITI Wagner; Masters Thesis
  • Inhalt: Viele Routing-Algorithmen für öffentliche Verkehrsnetzwerke beschränken die Länge von Fußwegen, die zwischen Stationen erlaubt sind. Es wird oft argumentiert, dass lange Fußwege nur selten die Reisezeit verbessern und deswegen nicht repräsentiert werden muss. Diese Annahme wurde jedoch kürzlich in Frage gestellt. Auf der anderen Seite verwenden existierende Algorithmen, die unbeschränktes Laufen erlauben, teure Dijkstra-Suchen, um die Fußwege zu erkunden, und sind deshalb deutlich langsamer als Algorithmen mit beschränktem Laufen. Diese Arbeit beschäftigt sich deshalb damit, schnellere Routing-Algorithmen für öffentliche Verkehrsnetzwerke mit unbeschränktem Laufen zu entwickeln. Hierzu präsentieren wir eine Beschleunigungstechnik für den RAPTOR-Algorithmus, die benötigte Fußwege vorberechnet. Dadurch werden die Dijkstra-Suchen überflüssig und die Erkundung der Fußwege wird beschleunigt. Weiterhin stellen wir zwei Algorithmen vor, die an existierende Beschleunigungstechniken angelehnt sind, die für andere Szenarien entwickelt wurden: Route-Flags basiert auf Arc-Flags, während ML-RAPTOR Ideen von Customizable Route Planning und Connection Scan Accelerated aufgreift. Eine experimentelle Studie auf dem öffentlichen Verkehrsnetzwerk der Schweiz zeigt, dass die Vorberechnungstechnik für Fußwege eine deutliche Beschleunigung gegenüber existierenden Algorithmen aufweist, während Route-Flags and ML-RAPTOR nur eine geringe Beschleunigung erzielen.

On Aesthetic Functions in Visualizations of Text Variant Graphs

  • Date: Fri, 4 May 2018, 14:30
  • Location: SR 301
  • Speaker: Jonas Haas, ITI Wagner; Bachelors Thesis
  • Inhalt: Text variant graphs can assist the visualization of the differences and similarities between various texts. As a viewer is reading the original texts over the course of a text variant graph, it is important that readability of the paths given by the original texts is high. This thesis suggests aesthetic functions to improve this kind of readability in drawings of text variant graphs. Integer linear programs and a heuristic approach for implementing the metrics are provided, and the results of the optimization approaches are evaluated.

Load-Balancing for parallel Delaunay Triangulations

  • Date: Fri, 4 May 2018, 14:00
  • Location: SR 301
  • Speaker: Vincent Winkler, ITI Sanders; Bachelors Thesis
  • Inhalt: Calculating the Delaunay triangulation of large point clouds with over a million points is time-consuming. Point clouds of over a billion points may even require distributed memory. Previous work by Funke and Sanders ["Parallel d-D Delaunay Triangulations in Shared and Distributed Memory"] presents a novel parallel algorithm that calculates the Delaunay triangulation on shared or distributed memory. With more realistic inputs however, the algorithm has to reprocess about 5% of the triangulation due to its simple work division strategy. This bachelor's thesis addresses the issue to decrease the overhead and further speed up the triangulation algorithm. An elaborate load balancing approach that partitions the input point cloud in an additional preprocessing step is provided. To find the partitioning, the Delaunay triangulation of a small input sample is partitioned by a graph partitioning algorithm and the resulting partitioning is extended to a partitioning of the entire input. Different extension strategies are developed and examined for the overall runtime, the reprocessing overhead and the balance of the partition sizes. The number of multiply processed points can be reduced to less than 0.5%. Partition sizes that deviate less than 1% from each other can be achieved.

Beobachtungen des Maximalen Flexiblen Drehstromübertragungssystem Flusses

  • Date: Wed, 2 May 2018, 13:00
  • Location: SR 301
  • Speaker: Larisa Duczek, ITI Wagner; Diplomarbeit
  • Inhalt: Diese Diplomarbeit beschäftigt sich mit der Auswirkung von flexiblen Drehstromübertragungssystemen (FACTS) auf den maximalen Leistungsfluss in speziellen Netzwerken, den Kaktusnetzwerken. FACTS-Geräte erhöhen die Impedanz (Wechselstromwiderstand) auf Stromleitungen und verändern somit den Leistungsfluss. Das ermöglicht eine Erhöhung des maximalen Leistungsflusses in einem Stromnetz. Ein Kaktusnetzwerk ist ein Netzwerk, dessen Leitungen Teil höchstens eines Kreises sind. In dieser Diplomarbeit wird ein lineares Gleichstrommodell, eine Approximation des Wechselstrommodells, als Berechnungsgrundlage benutzt. Es wird der Unterschied zwischen FACTS und dem maximalen Übertragungsschaltungsfluss erläutert. Es konnte beobachtet werden, dass in manchen Netzwerken eine Mischung aus FACTS und Übertragungsschaltungen sinnvoll ist. Zudem wird gezeigt, wie groß die Auswirkungen eines FACTS auf speziellen Kreisen mit einem Erzeuger und einem Verbraucher sind.

Aesthetic Value of Graph Layouts: Investigation of Statistical Syndromes for Automatic Quantification

  • Date: Tue, 24 Apr 2018, 13:00
  • Location: SR 301
  • Speaker: Moritz Klammler, ITI Wagner; Masters Thesis
  • Inhalt: Visualizing relational data as drawing of graphs is a technique in very wide-spread use across many fields and professions. While many graph drawing algorithms have been proposed to automatically generate a supposedly high-quality picture from an abstract mathematical data structure, the graph drawing community is still searching for a way to quantify the aesthetic value of any given solution in a way that allows one to compare graph layouts created by different algorithms for the same graph (presumably to automatically choose the better one). We believe that one promising path towards this goal could be enabled by combining data analysis techniques that have proven useful in other scientific disciplines that are dealing with large structures such as astronomy, crystallography or thermodynamics. In this work we present an initial investigation of some statistical properties of graph layouts that we believe could provide viable syndromes for the aesthetic value. As a proof of concept, we used machine learning techniques to train a neural network with the results of our data analysis and thereby built a model that is able to discriminate between better and worse layouts with an accuracy of 95 %. A rudimentary evaluation of the model was performed and is presented. This work primarily provides an infrastructure to enable further experimentation on the topic and will be made available to the public as Free Software.

Fall 2017

Hypergraph Clustering

  • Date: Thu, 29 Mar 2018, 14:00
  • Location: SR 301
  • Speaker: Hrudaya Ranjan Sahoo, IIT Matras; Masters Thesis Progress Report
  • Inhalt: To appear.

Communication-free Massively Distributed Graph Generation

  • Date: Thu, 15 Mar 2018, 14:00
  • Location: SR 301
  • Speaker: Sebastian Lamm, ITI Sanders; IPDPS Probevortrag
  • Inhalt: Analyzing massive complex networks yields promising insights about our everyday lives. Building scalable algorithms to do so is a challenging task that requires a careful analysis and an extensive evaluation. However, engineering such algorithms is often hindered by the scarcity of publicly available datasets. Network generators serve as a tool to alleviate this problem by providing synthetic instances with controllable parameters. However, many network generators fail to provide instances on a massive scale due to their sequential nature or resource constraints. Additionally, truly scalable network generators are few and often limited in their realism. In this work, we present novel generators for a variety of network models commonly found in practice. By making use of pseudorandomization and divide-and-conquer schemes, our generators follow a communication-free paradigm. The resulting generators are often embarrassingly parallel and have a near optimal scaling behavior. This allows us to generate instances of up to 2^43 vertices and 2^47 edges in less than 22 minutes on 32768 cores. Therefore, our generators allow new graph families to be used on an unprecedented scale.

Engineering a Compact Bit-Sliced Signature Index for Approximate Search on Genomic Data

  • Date: Mon, 26 Feb 2018, 14:00
  • Location: SR 236
  • Speaker: Florian Gauger, ITI Sanders; Masters Thesis
  • Inhalt: In recent years there has been an exponential increase in publicly available DNA data. This data encodes a huge amount of information on the ancestry of organisms, their evolution, and their abilities and properties. Until recently, it was not possible to search this data in its entirety. Providing online search facilities would enable research into epidemiology, basic science of disease, and antimicrobial resistance. Such search would be as enabling for microbial genomics as natural text search engines are for many everyday tasks. Recently the Bitsliced Genomic Signature Index was introduced enabling the search on all viral and bacterial genomic sequence reads in the European Nucleotide Archive as of December 2016 (447,833 genomes, 170 TiB). However, longer queries can take up to half an hour on a high performance machine. In this thesis we introduce the Compact Bit-Sliced Signature Index, a new index variant with significantly improved space and time requirements. In our empirical evaluation we show that execution time is improved by two orders of magnitude while space requirements are cut in half. For longer queries the execution time can be reduced from half an hour to under five seconds. Additionally, we enrich the query results with quality information which can be used for ranking the result set.

On Ortho-Radial Drawings for Metro Networks

  • Date: Wed, 21 Feb 2018, 11:00
  • Location: SR 301
  • Speaker: Benjamin Niedermann, ITI Wagner; Guest from the University of Bonn (Institute for Geodesy and Geoinformation)
  • Inhalt: Metro maps are schematic maps illustrating metro networks of cities. In contrast to road maps, the focus lies on the visualization of the network topology rather than on the geographic rendering of the network. Hence, when drawing a metro network, the algorithmically complex problem of finding a good network layout arises. Lately, concentric circles maps of metro networks have gained attention. Such drawings can be considered as grid drawings in the plane, where the grid is formed by concentric circles and straight-line spokes emanating from the circles' center. In this talk we present first steps towards an approach for automatically generating such ortho-radial drawings of metro networks.

High Quality Hypergraph Partitioning via Max-Flow-Min-Cut Computations

  • Date: Fri, 16 Feb 2018, 14:00
  • Location: SR 301
  • Speaker: Tobias Heuer, ITI Sanders; Masters Thesis
  • Inhalt: In this thesis, we introduce a framework based on Max-Flow-Min-Cut computations for improving balanced k-way partitions of hypergraphs. Currently, variations of the FM heuristic [17] are used as local search algorithms in all state-of-the-art multilevel hypergraph partitioners. Such move-based heuristics have the disadvantage that they only incorporate local information about the problem structure and if many moves of vertices have an equal impact on the solution quality, the outcome mainly depends on random choices made within the algorithm [15, 31, 36]. Flow-based approaches are not move-based and they are able to find a global minimum cut separating two vertices s and t [18]. Our framework is inspired by the work of Sanders and Schulz [44] who successfully integrate a flow-based refinement algorithm into a multilevel graph partitioner. We generalize many ideas such that they are applicable in the multilevel hypergraph partitioning context. We develop several techniques to sparsify the hypergraph flow network, which reduces the resulting problem size by a factor of 2 on average compared to the state-of-the-art representation [33]. Additionally, we show how to configure a flow problem on a subhypergraph such that the quality achievable with a Max-Flow-Min-Cut computation is significantly better than with the modeling approach of Sanders and Schulz. Finally, we integrate our work as refinement strategy into the n-level hypergraph partitioner KaHyPar [25]. We tested our framework on a large benchmark set with 3216 instances. In comparison to 5 different systems, our new configuration outperforms the tested state-of-the-art hypergraph partitioners on 73% of the instances. In comparison to the latest version of KaHyPar, our new approach improves quality by 2.5% while only incurring a performance slowdown by a factor of 2. However, our algorithm is still as fast as the direct k-way version of hMetis and outperforms it on 84% of the benchmarks.

Visualizing Opinion Space - Interactive Geographic Map Representations for Dynamic Opinion Datasets

  • Date: Fri, 19 Jan 2018, 14:00
  • Location: SR 301
  • Speaker: Sophie von Schmettow, ITI Wagner; Masters Thesis
  • Inhalt: Regarding large datasets, humans often have to rely on visualization methods in order to make sense of and extract relevant information from them. Kobourov et al. propose to depict relational data in the form of geography-like maps to create highly intuitive and readable visualizations that show clustering and neighbourhoods explicitly. In this work we explore how this idea can be used for structuring, analysing, and visualizing large bodies of opinion data, as they arise from large public debates. We develop OpMap, a tool to create interactive dynamic map representations of the argumentatively structured opinion landscape, which allows users to input and locate their own opinion. First, we specify a formal model of the space of opinions and evaluate various possibilities to measure semantic distances between them. In particular, we extract a graph from the opinion data where edge weights between opinion vertices are given by the degree of mutual coherence. The latter is a well studied measure in Bayesian epistemology, which renders the notion that coherent propositions support each other formally precise in probabilistic terms. We then investigate which clustering and graph drawing algorithms can be combined with such metrics in practice. The final tool uses infomap community detection in conjunction with a force-directed layout algorithm. To test the effectiveness of OpMap, we use simulated opinion datasets and collect an empirical sample of opinions on eating behaviours. Thereby we illustrate that semantic proximity in the data is captured well in the resulting maps.

Aligned Drawing of Plane Level Graphs

  • Date: Mon, 18 Dec 2017, 14:00
  • Location: SR 236
  • Speaker: Lars Gottesbüren, ITI Wagner; Masters Thesis
  • Inhalt: A level graph is a directed graph G=(V,E) with an assignment of vertices to levels lvl. In a level-planar drawing every vertex v is drawn on its level, the horizontal line y = lvl(v) and every edge is drawn as a y-monotone curve so that no two curves intersect in the interior. A pseudoline through a level-planar drawing is a simple y-monotone curve which intersects every edge at most once or fully covers it. It intersects every level exactly once, starts below the lowest level and ends above the topmost level. Let G be a graph with topological level-planar drawing and let A be an arrangement of pseudolines intersecting G. In this thesis we study (straight-line) aligned level drawings T, A), where T is a level-planar (straight-line) polyline drawing of G, A is an arrangement of y-monotone straight lines homeomorphic to A, and T and A intersect in the same way as G and A. Mchedlidze et al. consider aligned drawings in planar graphs, and prove that every stretchable pseudoline arrangement intersecting a topologically embedded planar graph, where every edge is either fully covered or intersected at most once by a pseudoline, admit a straight-line aligned drawing. Deciding whether (G,A) and given A, admit a straight-line aligned level drawing (T,A), is the Straight-Line Aligned Level Drawing problem, for which we propose a polynomial-time algorithm, based on linear programming. Additionally, we present an asymptotically optimal algorithm for graphs with two levels, which solves the problem by reduction to a novel geometric problem. Furthermore, we show that there always is an aligned level drawing such that every edge is bent only where it is intersected by a pseudoline. Moreover, we study a problem called Intersection Sequence Embedding. Its input is a level graph G without an embedding, a pseudoline arrangement A intersecting the levels of G, and a description of how A and G are supposed to intersect. The problem then asks whether G has a topological level drawing without edge crossings, which realizes the desired intersection. To solve it, we propose a linear-time reduction to testing level planarity, for which linear-time algorithms are known (Jünger et al.).

A Unified Framework for Electric Vehicle Routing

  • Date: Fri, 15 Dec 2017, 14:00
  • Location: SR 301
  • Speaker: Patrick Niklaus, ITI Wagner; Masters Thesis
  • Inhalt: Route planning is an integral part of our daily lives and industries. Because we will see a transition from fossil fuel based vehicles to electric vehicles in the coming years, we want to update the models we use for route planning to this development. A limited number of charging stations, small battery capacities and long charging times make it necessary to incorporate a consumption model when computing optimal travel times. The consumption model of an electric vehicle needs to account for effects like non-linear charging rates of Lithium-Ion batteries and energy recuperation. We will present an accurate consumption model that incorporates the option of driving slower, with a realistic charging model for batteries. Based on that, we present an algorithm to compute exact solutions and augment it with an A*-based speedup technique to enable computing solutions on country-sized datasets in a sensible time and evaluate the results.


  • Date: Fri, 8 Dec 2017, 14:00
  • Location: SR 301
  • Speaker: Reserviert von Herrn Griesbaum, Reserviert von um 14 Uhr bis um 15:30 Uhr
  • Inhalt: -

Constructing Cuckoo hash tables independent of their load-factor

  • Date: Tue, 28 Nov 2017, 13:30
  • Location: SR 301
  • Speaker: Henning Schulze, ITI Sanders; Bachelors Thesis
  • Inhalt: A bucketized Cuckoo hash table is a hash table which is divided in disjunctive buckets containing k elements each. Each element is stored in a bucket dictated by one of two hash functions. Cuckoo hash tables guarantee a constant worst-case access-time. Bucketized Cuckoo hash tables additionally support very high load-factors. This thesis presents multiple algorithms to construct such a bucketized Cuckoo hash table, based on the Selfless(k)-algorithm [CaSaWo2007]. Our algorithms work directly on the table. Thereby, we achieve algorithms that use sublinear memory and whose running time is independent of the load-factor. We also present highly efficient parallel versions of our algorithms. Additionally, we combine the d-ary Cuckoo hashing [FPSS2003] approach with bucket Cuckoo hashing by adapting the Selfless(k)-algorithm [CaSaWo2007] to be used with multiple hash functions instead of two. We show the performance in a number of benchmarks and compare our algorithms to a growing and non-growing state of the art iterated insertion algorithm.

A Practical, Compact Representation for Plane Triangulations

  • Date: Tue, 28 Nov 2017, 13:00
  • Location: SR 301
  • Speaker: Philip Zander, ITI Sanders; Bachelors Thesis
  • Inhalt: Triangulations, or triangular graphs, are a decomposition of a point set into triangles. They have many uses in computer science, ranging from computer graphics to scien- tific simulations. The related class of planar graphs has applications in e.g. microchip design and route planning. The research area of compact data structures (or succinct data structures) deals with the problem of representing data structures with as few bits as possible, i.e. close to the information-theoretical limit. The information-theoretically optimal encoding for a triangulation uses 3.24 bits per vertex. This encoding is how- ever not practical because there is no known algorithm to construct it efficiently or perform useful operations on it. We implement an encoding based on orderly span- ning trees that uses 6 bits per vertex, can be constructed in linear time, and supports adjacency, clockwise neighbor and counter-clockwise neighbor queries for vertices in asymptotically constant time with few extra bits.

On the Complexity of Public Transit Profile Queries

  • Date: Mon, 13 Nov 2017, 13:30
  • Location: SR 236
  • Speaker: Florian Grötschla, ITI Wagner; Bachelors Thesis
  • Inhalt: TBA

Optimierung von Routen für spontane Zieländerung

  • Date: Mon, 13 Nov 2017, 13:00
  • Location: SR 236
  • Speaker: Michael Schrempp, ITI Wagner; Bachelors Thesis
  • Inhalt: In dieser Arbeit geht es um Routen, bei denen sich das Fahrtziel plötzlich ändern kann. Die alte Route wird dann verworfen. Die Zielsetzung ist es, auf Basis der von uns berechneten Routen, möglichst "gut" auf diese Änderungen reagieren zu können. Was "gut" genau bedeutet, hängt vom Anwendungsfall ab. Diese Art der Routenplanung kann in verschiedenen Bereichen nützlich sein. In dieser Arbeit wurde das Hauptaugenmerk auf den Rettungsdienst gelegt. Die Arbeit befasst sich mit dem Entwurf und der experimentellen Analyse von möglichen Rückfahrstrategien. Es werden sowohl der aktuelle Stand der Technik als auch selbst entworfene Strategien getestet und bewertet. Schlussendlich werden alle Optionen verglichen und betrachtet, wofür sich welche Strategie eignet.

Graph-theoretical Characterizations of Metropolitan Areas

  • Date: Fri, 10 Nov 2017, 14:30
  • Location: SR 301
  • Speaker: Friedrich Schroedter, ITI Sanders; Masters Thesis
  • Inhalt: This paper introduce a graph based calculation of metropol cities. The calculation based on the german street routing network and the german population in a grid of 100m × 100m. The metropols are descriped as a quasi-voronoi-region on the street graph. In this work it is shown how to assign the population to the nodes of a region that stands for a metropol and how to calculate the biggest metropol of that network.

Tracking of Communities in Social Networks

  • Date: Fri, 10 Nov 2017, 14:00
  • Location: SR 301
  • Speaker: Paul Skopnik, ITI Meyerhenke; Bachelors Thesis
  • Inhalt: Social networks are ubiquitous. These networks have been shown to exhibit community structures, that is a grouping of individuals into clusters. Community detection in static networks is a well-covered topic. However, social networks are inherently dynamic, as the interactions between their members often change. That means that the community structure incessantly evolves as well. We present an approach to tracking communities based on finding many-to-many correspondences between snapshots of a network at different times. By exploring a minimum cut basis represented as a Gomory-Hu tree, we extract a set of small, interesting correspondences, representing events in the evolution of communities. We use this method to visualise dynamic networks in a time-graph as a history of their communities' transformations. Furthermore, we present an approach for detecting super-cluster patterns in the evolution of the network. We find sets of communities with an elevated affinity towards each other by aggregating the transformations we observed. To demonstrate the feasibility of our approaches, we develop the dynamic communities generator, a model for generating dynamic networks of evolving communities. It maintains the network as a set of clusters made of sub-clusters, which undergo probabilistic split and merge transformations. Super-cluster patterns are exhibited, because probabilities adhere to an affinity matrix. Experiments on the thereby created networks show the resistance of our tracking methods to background noise as well their resistance to even substantial structural transformations between consecutive snapshots. Likewise, given a significant number of snapshots, our super-cluster detection proves successful at reconstructing the shape of the affinity matrix.

Engineering Multimodal Transit Route Planning

  • Date: Fri, 10 Nov 2017, 13:30
  • Location: SR 301
  • Speaker: Huyen Chau Nguyen, ITI Wagner; Masters Thesis
  • Inhalt: TBA

Sparsity and Dimension

  • Date: Fri, 3 Nov 2017, 14:00
  • Location: SR 301
  • Speaker: Piotr Micek, ITI Wagner; Guest from the Jagiellonian University
  • Inhalt: Partially ordered sets, posets for short, are studied extensively in combinatorics, set theory and theoretical computer science. One of the most important measures of complexity of a poset is its dimension. Not surprisingly, dimension is hard to compute: Already deciding whether dim(P) <= 3 is an NP-hard problem (Yannakakis 1982), and for every epsi>0, there is no n^{1-epsi}-approximation algorithm for dimension unless ZPP=NP, where n denotes the size of the input poset (Chalermsook et al 2012). Research in this area typically focus on finding witnesses for large dimension and sufficient conditions for small dimension. Posets are visualized by their diagrams: Points are placed in the plane and whenever a

Extending drawings with fixed inner faces with and without bends

  • Date: Thu, 26 Oct 2017, 13:00
  • Location: SR 301
  • Speaker: Jérôme Urhausen, ITI Wagner; Masters Thesis
  • Inhalt: The focus of the thesis is the problem of extending the drawing of an inner face of a given embedded graph to a drawing of the entire graph using piecewise-linear edges while minimizing the amount of bends per edge. The talk will go through the results of the thesis. Among others we prove that every drawing of a face as a star can be extended to a drawing of the entire graph using at most one bend per edge. Continuing in the same spirit we define b-outer stars as a complexity measure using visibility distance from the outside. We show that a face drawn as such a polygon can be extended with at most b+log_2(n)+1 bends per edge, where n is the amount of vertices of the polygon.

Engineering FPT-based Edge Editing Algorithms

  • Date: Tue, 24 Oct 2017, 13:15
  • Location: SR 301
  • Speaker: Sven Zühlsdorf, ITI Wagner; Masters Thesis
  • Inhalt: In dieser Arbeit betrachten wir Algorithmen die das F-free Edge Editing Problem lösen, wobei F eine Menge an verbotenen Teilgraphen bezeichnet. Wir entwickeln den Redundant Editing Algorithm als Verbesserung des von [Cai '96] vorgestellten FPT-Algorithmus. Die Zeitkomplexität des Algorithmus wird nicht verbessert, jedoch beweisen und evaluieren wir die praktischen Vorteile. Wir stellen fest, dass der Redundant Editing Algorithm mehrere Größenordnungen schneller ist. Dieser Vorteil wächst mit zunehmender Komplexität des Eingabegraphen. Kanteneditierungsalgorithmen basierend auf [Cai '96] benötigen eine Strategie zur Auswahl verbotener Teilgraphen. Wir stellen "single edge editing" als Alternative zu solchen Strategien vor. Unter bestimmten Bedingungen können wir damit das Kanteneditierungsproblem für ein gegebenes F in O(4^k poly(n)) lösen. In unserer Evaluation, in der wir F = {P4, C4} als Menge von verbotenen Teilgraphen verwenden, stellen wir fest, dass wir drei der von [Nastos & Gao '13] benutzten Graphen innerhalb von Minuten lösen können. Zwei dieser Graphen waren bisher ungelöst.

Smart Local Search in Hypergraph Partitioning

  • Date: Tue, 17 Oct 2017, 13:00
  • Location: SR 301
  • Speaker: Orlin Kolev, ITI Sanders; Diploma Thesis
  • Inhalt: Hypergraphs are a generalisation of graphs where each (hyper)edge can connect more than two vertices. Partitioning hypergraphs in disjoint, balanced blocks with low connectivity in between is a problem with many applications, for example VLSI CAD and scientic computing. Since it is NP-hard, it is solved using various heuristics. State of the art partitioners use a multilevel approach, in which the partitioning is done in three stages: coarsening, when vertices are contracted together in a way that preserves the structure of the graph, initial partitioning, and nally uncoarsening and renement. During the renement stage, a local search heuristic is used that improves the current partitioning each time after an uncontraction. The most commonly used heuristic for the local search is the Fiduccia-Mattheyeses algorithm. Various improvements have been made to it over time, but most of them focus on improving runtime. In this work we explore ways to improve the quality of solutions by modifying FM to take into account more information about the graph. We applied and modied some algorithms from the literature and developed a new one, integrating all into KaHyPar, a high-quality universal hypergraph partitioner. Our experiments showed a pronounced improvement against the original implementation of FM and our new method, Interval Soft Gain, achieves some of the best overall results and outperforms other approaches for some instance classes.

Optimal Route Planning for Hitchhiking

  • Date: Tue, 10 Oct 2017, 14:00
  • Location: SR 010
  • Speaker: Alex Vedernikov, ITI Wagner; Guest from the University of Melbourne
  • Inhalt: Hitchhiking is the oldest ridesharing process without prior arrangements with drivers. It usually involves uncertain waiting times and various combinations of lifts on roads. The problem of finding an optimal route for hitchhikers will be presented. We consider time-independent and time-dependent hitchhiking problems and propose concepts of hitchhiking graphs and hypergraphs to formulate and solve them. The experiments on road networks of selected countries will be presented.

On Interval Planar Graphs

  • Date: Fri, 6 Oct 2017, 14:00
  • Location: SR 010
  • Speaker: Paul Jungeblut, ITI Wagner; Bachelors Thesis
  • Inhalt: Upward Planarity is a problem asking for a planar drawing of a directed graph such that each edge is a y-monotone curve. In Level Planarity we ask for an upward planar drawing where each vertex has a fixed y-coordinate previously assigned to it. We will close the gap between Upward Planarity and Level Planarity by introducing a new, more general problem that we call Interval Planarity. In this problem we ask for an upward planar drawing of a directed graph G=(V,E), such that each edge is a y-monotone curve and each vertex has its y-coordinate from an interval that was previously assigned to it. We show NP-completeness of the problem in its general form and consider several restricted variants that allow an efficient upward planarity test, because this is a necessary condition. We describe embedding algorithms for st-planar graphs and single source graphs with a fixed combinatorial embedding in O(|V|) time and cycles in O(|V|^5) time. Further we show that the problem remains NP-complete, even if a combinatorial embedding is fixed or the graph is restricted to be a tree, single source or outerplanar. We finish by showing that Interval Planarity is also NP-complete when we bound the maximum number of vertices with the same y-coordinate, even for st-planar graphs or very simple trees.

Spring 2017

An Optimal Algorithm for Approximate Minimum Selection with Unreliable Comparisons

  • Date: Tue, 19 Sep 2017, 14:00
  • Location: SR 236
  • Speaker: Chih-Hung Liu, ITI Wagner; Guest from the ETH Zurich
  • Inhalt: We consider the approximate minimum selection problem in the independent random comparison faults model. We want to select one of the smallest $k$ elements in a collection of n elements by only performing unreliable pairwise comparisons: whenever two elements are compared, there is constant probability that the wrong answer is returned. We design a randomized algorithm that solves this problem with high probability (w.h.p.) for the whole range of values of k using O(n/k log n) expected time. Then, we prove that the expected running time of any algorithm that succeeds w.h.p. must also be Omega(n/k log n), thus implying that proposed algorithm is optimal, in expectation. These results are quite surprising in the sense that for k between Omega(log n) and c times n, for any constant c<1, the expected running time is still Omega( n/k log n) even in absence of comparison faults. Loosely speaking, we show to how deal with comparison errors without any substantial complexity penalty w.r.t. the fault-free case!

Peak Demand Scheduling For One Resource

  • Date: Fri, 11 Aug 2017, 14:30
  • Location: SR 301
  • Speaker: Jingxian Wu, ITI Wagner, Bachelors Thesis
  • Inhalt: With the addition of renewable generation in the smart grid and the difficulty of generation responding to changes in demand, the goal has been changed to demand matching supply in the modern power grid. The cost of generation and distribution of resources will be reduced if the daily load curve from customers keep as flat as possible. So how to schedule the power-requesting jobs to minimize the peak power demand is very important. Furthermore, job scheduling is often used in the computer science or our daily life, so the solution to the problem of minimizing resources of a schedule is very practical. In this work, we consider two variations on the classic job scheduling problem in which the goal is to minimize the peak resource demand of a schedule. We also consider two existing algorithms to solve these two problems, respectively. One is an effective heuristic algorithm, the other is an optimal algorithm based on branch-and-bound procedure. We implement and optimize these two algorithms. Simulation results using a series of instances show that our algorithms have less execution time and better quality of the result.

Clusteringansätze von Windfarmen

  • Date: Fri, 11 Aug 2017, 14:00
  • Location: SR 301
  • Speaker: Hannah Wenk, ITI Wagner, Bachelors Thesis
  • Inhalt: In meiner Bachelorarbeit habe ich Algorithmen zur Berechnung Kabellayoutproblems für Windfarmen mit Graphclustering entwickelt. Dies bedeutet die Verkabelung innerhalb einer Windfarm zwischen den Windenergieanlagen (WEA) und dem Um- spannstationen, die Problematik besteht dabei sowohl darin welche Komponenten miteinander verbunden werden als auch welche Kbael verwendet werden. Dabei habe ich mehrere Varianten eines Moveralgorithmus implementiert und mit den Ergebnissen durch Multilevel Quality Threshold Clustering sowie durch ein Mixed Integer Linear Program verglichen. Die Moveralgorithmen waren dabei ähnlich gut wie das MILP dabei aber deutlich schneller, Instanzen bis 300 WEA konnten in unter 15 Minuten gelöst werden.

Incremental SAT Solving for SAT Based Planning

  • Date: Thu, 10 Aug 2017, 15:00
  • Location: SR 301
  • Speaker: Stephan Gocht, ITI Sanders, Master Thesis
  • Inhalt: One of the most successful approaches to automated planning is the translation to propositional satisfiability (SAT). This thesis employs incremental SAT solving to increase the capabilities of several modern encodings for SAT based planning.

Drawing graph with high crossing resolution

  • Date: Tue, 25 Jul 2017, 13:00
  • Location: SR 301
  • Speaker: Almut Demel, Dominik Dürrschnabel, Lasse Wulf, ITI Wagner, Graph Drawing Practical Course
  • Inhalt: The crossing resolution of a graph drawing refers to the smallest angle formed by any two crossing edges. Empirical studies on readability of graph drawings suggest that increase in crossing resolution contributes to better readability. On the other hand, testing whether a graph has a drawing with crossing resolution of 90 degrees is an NP-hard problem. In this practical course, we studied the related work, and then implemented several existing and new heuristics to construct drawings with good crossing resolution. We experimentally compared the performance of these heuristics. In this talk we will present the compared algorithms and their experimental evaluation.

Task Mapping in a Distributed Setting

  • Date: Tue, 18 Jul 2017, 13:00
  • Location: SR 301
  • Speaker: Marius Dörner, PARCO Meyerhenke, Bachelors Thesis
  • Inhalt: Modern HPC-systems become increasingly more heterogeneous with multiple types of processing elements that differ in their computational and memory capacities. Thus, mapping algorithms that distribute data of parallel applications on these systems need to comply with new constraints, e.g. the memory capacities of processing elements. The aim of task mapping is to minimize communication during the runtime of the application. We present a distributed mapping algorithm that assigns partitions of a mesh, represented by a graph with coordinates embeddings, to the nodes of a processor graph, representing the topology of the HPC-system. The algorithm uses an implicit approach where mapping and partitioning is combined into one step. We present two partitioning algorithms, a greedy and a dynamic programming approach, that partition the input graph along a space-filling curve without violating the constraints of the mapping problem. Partitions are refined by a parallel Fiduccia-Mattheyses algorithm. For our experimental environment, we measured the latency and bandwidth between processes on a HPC-cluster. Our experiments show that we can create mappings for big graphs efficiently, e.g. it took about 10 seconds to partition a mesh with about 8 million nodes.

Ant-based Algorithms for the Wind Farm Cable Layout Problem

  • Date: Fri, 30 Jun 2017, 14:30
  • Location: SR 301
  • Speaker: Jakob Nedlin, ITI Wagner, Bachelors Thesis
  • Inhalt: In the design of offshore wind farms the transport of energy though cable connections is an important aspect as the required cables are a high cost factor that needs to be optimized. When planning a wind farm the construction of a cost efficient cabling layout between the turbines and substations is an important step. Such cabling optimization problems are NP-hard. As a consequence we have to rely on heuristic or approximation algorithms for calculating satisfying solutions. Ant Colony Optimization is a heuristic optimization algorithm inspired by the behavior of real ants. In this thesis we present four different ant-based algorithms for solving the wind farm cabling layout problem. To investigate this problem we use a wind farm model with fixed turbine and substation positions as input. Given a set of cable types with different capacities and costs we want to find an optimal cabling system with minimal costs. We compare our algorithms to a benchmark algorithm using Mixed Integer Linear Programming (MILP) representation. We will see that our ant-based algorithms generate better results than the MILP for some smaller instances. Our best ant-based approach is using a representation similar to Kruskal's algorithm. For larger instances our proposed algorithms perform worse than the MILP, but we give suggestions how to build an improved algorithm based on our results.

Entwicklung eines genetischen Algorithmus zur effizienten Verkabelung von Windfarmen

  • Date: Fri, 30 Jun 2017, 14:00
  • Location: SR 301
  • Speaker: Ivo Baar, ITI Wagner, Bachelors Thesis
  • Inhalt: Windfarmen sind ein wichtiger Zweig der erneuerbaren Energien. Es werden zunehmend neue Projekte geplant. Einen großen Teil der Kosten einer Windfarm nimmt die Verkabelung der Turbinen ein. Da das Problem der Minimierung dieser Kosten NP-schwer ist, werden algorithmische Lösungen zur Approximation benötigt. In dieser Arbeit wird daher ein genetischer Algorithmus vorgestellt, der sich diesem Problem widmet. Dafür wird eine Repräsentation einer Verkabelung gewählt. Mehrere dieser Repräsentationen bilden dann eine Population, die durch genetische Operatoren iterativ verändert wird. Diese Operatoren selektieren, mutieren und rekombinieren diese repräsentierten Individuen der Population und minimieren dadurch deren Kosten. Viele Algorithmen, die für dieses Problem vorgestellt wurden, konzentrieren sich auf kleinere Windfarmen. Die Turbinenzahlen steigen jedoch stetig an und immer größere Projekte werden geplant. Daher wird in dieser Arbeit auf einem Benchmark Datenset getestet, das, auch für heutige Verhältnisse, große Windfarmen enthält. Als Referenz wird ein MILP-basierter Algorithmus herangezogen, mit dem die Ergebnisse verglichen werden. Vor allem für Windfarmen mit bis zu 200 Turbinen schneidet der vorgestellte Algorithmus, sogar mit geringerer Laufzeit, besser ab.

Engineering Distributed Graph Clustering using MapReduce

  • Date: Tue, 27 Jun 2017, 13:00
  • Location: SR 301
  • Speaker: Tim Zeitz, ITI Wagner, Master Thesis
  • Inhalt: Detecting community structures in networks is an important problem in graph analytics. With the recent BigData trends network sizes are growing tremendously. Oftentimes the networks are now too big for the RAM of a single computer. This leads to the need for distributed graph clustering algorithms. In this presentation, two MapReduce based algorithms are introduced. They build upon the well-known Louvain algorithm. They were implemented in Thrill, a new experimental BigData batch processing framework. The evaluation shows that the algorithms can cluster graphs with tens of billions of edges in a few hours while still delivering quality similar to the original Louvain algorithm.

Simultane Kreissehnengraphen

  • Date: Wed, 21 Jun 2017, 14:00
  • Location: SR 236
  • Speaker: Marianne Petersen, ITI Wagner, Master Thesis
  • Inhalt: Problemstellungen für Schnittgraphen sind ein zentrales Forschungsthema der algorithmischen Graphentheorie. Eine Klasse von Schnittgraphen sind die Kreissehnengraphen, welche jeweils durch eine Schnittrepräsentation von Sehnen in einem Kreis dargestellt werden können, ein sogenanntes Sehnendiagramm. Ein entscheidendes Werkzeug um die Struktur von Kreissehnengraphen zu analysieren ist die Splitzerlegung. Diese kann als Baum beschriftet mit den Teilen der Splitzerlegung aufgefasst werden und wird Splitbaum genannt. Die Erkennung von Kreissehnengraphen ist in quasi-linearer Zeit möglich. Jedoch sind einige Erkennungsprobleme mit zusätzlichen Einschränkungen, wie das simultane Kreissehnengraphenproblem, im Allgemeinen NP-schwer. Bis jetzt gab es nur Ansätze mit polynomieller Laufzeit um das Erweiterungsproblem zu lösen, welches ein Teilproblem des simultanen Kreissehnengraphenproblems ist. Diese Arbeit löst für einen zusammenhängenden und ausschließlich in prime Teile zerlegbaren Schnittgraphen das simultane Kreissehnengraphenproblem für beliebig viele Eingabegraphen in Polynomialzeit. Dafür werden drei neue Werkzeuge vorgestellt.Es wird eine bijektive Abbildung zwischen den Sehnendiagrammen eines Graphen und einer bestimmten Wahl für jeden Knoten und jeder Kante des Splitbaums definiert. Damit gibt es erstmals die Möglichkeit die Menge aller Sehnendiagramme eines Kreissehnengraphen auf eine leichter verständliche und strukturierte Menge abzubilden. Zusätzlich wird die Beziehung zwischen den Splitbäumen eines Graphen und eines Teilgraphen aufgezeigt. Schlussendlich kann das simultane Kreissehnengraphenproblem unter den genannten Einschränkungen auf ein 2-SAT-Problem reduziert werden.

Drawing Planar GitHub Network Graphs

  • Date: Tue, 6 Jun 2017, 13:00
  • Location: SR 301
  • Speaker: Rashad Asgarbayli, ITI Wagner, Bachelors Thesis
  • Inhalt: There is much work done on planar level graph drawing. In this thesis, an approach that involves the well known PQ-trees [BL76] is implemented to solve the problem for the single-source k-level graphs. To achieve this goal "Simple Level-Planarity Algorithm" represented by Brückner and Rutter [BR17] is implemented for testing a given single-source proper k-level graph for planarity in linear running time. Then, a “DrawPlanar Algorithm” is implemented, which generates one of the planar drawings of the given single-source k-level graph in linear running time, if the result of the testing with "Simple Level-Planarity Algorithm" confirms the planarity. After generating a planar drawing, an heuristic is used to improve the quality of the planar drawing, which is also implemented in this thesis.

More on Different Graph Covering Numbers Structural, Extremal and Algorithmic Results

  • Date: Fri, 2 Jun 2017, 14:00
  • Location: SR 301
  • Speaker: Peter Stumpf, ITI Wagner, Master Thesis
  • Inhalt: A covering number measures how "difficult" it is to cover all edges of a host graph with guest graphs of a given guest class. E.g., the global covering number, which has received the most attention, is the smallest number k such that the host graph is the union of k guest graphs from the guest class. In this thesis, we consider there cent framework of the global, the local and the folded covering number (Knauerand Ueckerdt, Discrete Mathematics 339 (2016)). The local covering number relaxes the global covering number by counting the guest graphs only locally at every vertex. And the folded covering number relaxes the local covering number even further, by allowing several vertices in the same guest graph to be identified, at the expense of counting these with multiplicities. More precisely, we consider a cover of a host graph H with regards to a guest class G to be a finite set of guest graphs $S = {G_1 , . . . , G_m } subset G$ paired with an edge-surjective homomorphism $phi : G_1 U · . . . U · G_m -> H$. The cover is called guest-injective, if for $i = 1, . . ., m$ its restricted homomorphism $phi|G_i$ is vertex-injective. The global covering number is thus the smallest number k such that there is a guest-injective cover with $|S| = k$. The local covering number is the smallest number k such that there is a guest-injective cover with $|phi^{-1} (v)| <= k$ for every vertex $v in H$. And the folded covering number is the smallest number k such that there is a (not necessarily guest-injective) cover with $|phi^{-1} (v)| <= k$ for every vertex $v in H$. In this thesis we investigate the relations between these numbers. As one result we show that the local covering number of any shift graph with regards to bipartite graphs is at most 2, while the corresponding global covering numberscan be arbitrarily large. This is the first known separation of local and global covering number with a subgraph-hereditary guest class. This concludes the study of separation results, as a separation of folded and local covering number with such a guest class was already known, as well as the fact that such a separation is not possible for union-closed topological-minor-closed guest classes. Furthermore, we investigate for 0 <= a and 0 <= b <= 2a - 1 the classes of (a, b)-sparse graphs as guest classes. For these local and global covering number always coincide. This generalises existing results for forests and pseudo-forests. We prove that the covering numbers with regards to these (a, b)-sparse graphs always match fairly simple lower bounds given by variations of the host graph's maximum average degree. We moreover provide efficient algorithms to calculate corresponding covers. Investigating the question, whether for the guest class of planar graphs the local and global covering number always coincide, we prove that determining the corresponding local coveringnumber is NP-hard. While most attention in the given framework focuses on properties for the guest classes, we also investigate graph classes of host graphs without fixing the guest class. Namely, we introduce a property called cover resistance. We call a class H of host graphs (f/l/g)-cover resistant, if the (folded/local/global) covering numbers for these host graphs usually become arbitrarily large. I.e., it is (f/l/g)-cover resistant, if for each union-closed induced-hereditary guest class G we have host graphs in H with arbitrarily large (folded/local/global) covering numbers, unless G contains H. For the classes of host graphs the relaxations of folded and local covering number are inverse, i.e., the f-cover resistance implies l-cover resistance which in turn implies g-cover resistance. We give examples for each of these resistances. Most notably, the class of all graphs is itself l-cover resistant, while only subclasses of bipartite graphs can be f-cover resistant.

Optimale Sensorplatzierung für Beobachtbarkeit in Multidomänen-Energieverteilnetzen

  • Date: Tue, 23 May 2017, 16:00
  • Location: Seminarraum 228 im Geb. 10.91.
  • Speaker: Carina Mieth, ITI Wagner and IRS Hohmann, Masters Thesis
  • Inhalt: In cause of the decentralization of the energy supply, passive single-carrier energy distribution grids (electricity, gas, district heat) are subject to a transition to active multi-carrier energy distribution systems (MEDSs). For an efficient and safe operation of MEDSs, operational variables need to be measurable or calculable, i.e. the system has to be observable. Hence, we study the problem of modelling and computing a cost-optimal sensor placement ensuring the MEDS to be observable. The approach is illustrated in a case study for a sub-grid of the MEDS of Karlsruhe, Germany.

A survey of network visualization in Humanities

  • Date: Tue, 23 May 2017, 13:00
  • Location: SR 301
  • Speaker: Rebecca Seelos, ITI Wagner, Bachelors Thesis
  • Inhalt: This thesis is a survey of network visualization techniques that are used in different fields of humanities. I will present rather recent examples that I found in various digital humanity and data visualization conferences of the last years. As the field of digital humanities is growing and visualizations techniques have promising applications, this work investigates the properties of networks and their visualizations in the humanities, and tries to answer the question of what techniques are useful to facilitate the research of humanty scholars.

Computing Top-k Closeness in Fully-dynamic Graphs

  • Date: Fri, 19 May 2017, 14:00
  • Location: SR 301
  • Speaker: Patrick Bisenius, PARCO Meyerhenke, Masters Thesis
  • Inhalt: Closeness is a widely-studied centrality measure in network analysis. Since it requires all pairwise distances, computing closeness centrality for all nodes is unfeasible for large real-world networks. However, for most applications, it is only necessary to find the k most central nodes and not all closeness values. Prior work has shown that computing the top-k nodes with highest closeness can be done much faster than computing closeness for all nodes in real-world networks. However, for networks that evolve over time, no dynamic top-k closeness algorithm exists that improves on static recomputation. In this thesis, we present several techniques that allow us to efficiently recompute the k nodes with highest closeness after an edge insertion or an edge deletion. Our algorithms use information obtained during earlier computations to skip unnecessary work. However, they do not require asymptotically more memory than the static algorithms (i.e. linear in the number of nodes). We propose separate algorithms for complex networks and networks with large diameter, such as street networks. For edge insertions in undirected complex networks, our average speedup on recomputation is about 40 and it is up to 160 for some graphs. For street networks, the average speedup is 70 and it is up to 150. For some edges, our algorithm is up to three orders of magnitude faster than static recomputation. We also study the problem of finding a group of k nodes with high closeness. We adapt a static greedy algorithm for the dynamic case. We use our dynamic algorithms for top-k closeness centrality and employ similar techniques to reduce the amount of computation. On average, our dynamic algorithm is between 8 and 15 times faster, depending on the group size.

Packet-Based Power Transmission

  • Date: Thu, 11 May 2017, 14:00
  • Location: Gebäude 50.31, Bauingenieure Hörsaal 107, Gotthard-Franz-Str. 3, 76131 Karlsruhe
  • Speaker: Dr. Bernd Reifenhäuser, ITI Wagner, Guest, Chief Executive of the GIP Exyr GmbH
  • Inhalt: The Quantum Grid is a packet-based energy distribution grid operating under a novel fundamental principle: power flow from a source to a destination is realized by the transmission of energy-packets and is only possible by a contract for energy-packet delivery. Each consumer needs to order energy-packets with the required power profile in order to cover his specific needs. Just as the Internet, the Quantum Grid will have a self-similar structure, is self-organized and operates decentralized. This implies inherent fail-safety. The new grid concept is particular suited for 100 % integration of renewable energies. Consumers are becoming producers (prosumers). Traditional roles break up and the centrally organized supply and control of todays' grid seems no longer adequate. The core element of a packet-based energy-grid is the Quantum Grid Router, enabling the transmission of energy-packets from a sender, through the grid to a receiver. An energy-packet is defined by a unique data-packet containing the full information of the energy packet. The power flow transmission in the Quantum Grid is accomplished by the routing of energy packets, allowing the simultaneous transmission of multiple energy-packets along the same link. Also storage devices will be an intrinsic part of the grid, where energy-packets can be stored and later retrieved. Only an electricity grid as the Quantum Grid will be able to meet the requirements of the digital world in the future and thus: lim_{t->infty} Smart Grid = Quantum Grid

Heursitiken zum Organisieren von Sitzungen

  • Date: Tue, 9 May 2017, 13:00
  • Location: SR 301
  • Speaker: Lukas Hennig, Bachelorarbeitsvortrag, ITI Wagner
  • Inhalt: Eine Gruppe von Leuten trifft sich, um gemeinsam an diversen Projekten zu arbeiten. Jede Person wirkt an einer Teilmenge der Projekte mit, kann aber immer nur an einem Projekt gleichzeitig arbeiten. Außerdem kann ein Projekt nur dann bearbeitet werden, wenn alle mitwirkenden Personen anwesend sind. Leider ist die verfügbare Zeit viel zu kurz, um alle Projekte umzusetzen. Es muss daher eine Auswahl getroffen werden. In dieser Arbeit wurden Algorithmen für dieses Problem experimentell untersucht. Es hat sich gezeigt, dass sich ganzzahlige lineare Programmierung zum Finden optimaler Lösungen nur für sehr kleine Probleminstanzen eignet. Daher wurden eine Reihe von Heuristiken entworfen und getestet. Untersucht wurden, neben einfachen Greedy-Heuristiken mit verschiedenen Auswahlkriterien, auch eine Heuristik, die das Problem für kleinere Teilprobleme löst, sowie ein Algorithmus, der eine gegebene Lösung mittels lokaler Suche weiter verbessert.

Berechnung kürzester Pfade mit einsammelbaren Zeitgutschriften

  • Date: Tue, 2 May 2017, 13:00
  • Location: SR 301
  • Speaker: Florian Brinkschulte, ITI Wagner, Bachelor Thesis
  • Inhalt: Gegeben ist ein positiv gewichteter, gerichteter Graph, ein Start- und ein Zielknoten sowie eine Menge von einsammelbaren Zeitgutschriften, welche auf den Knoten des Graphen verteilt sind. Gesucht wird der kürzeste Pfad vom Start- zum Zielknoten. Dabei gilt für die Länge eines Pfades, dass sich diese um das Gewicht der Zeitgutschriften verringert, über welche der Pfad verläuft. Dieses Problem wird in ein Problem umgewandelt, bei dem auf einem vollständigen Graphen ein kürzester zyklenfreier Pfad vom Start- zum Zielknoten gesucht wird. Die Knoten des Graphen repräsentieren die Zeitgutschriften sowie den Start- und den Zielknoten. Für dieses Problem wurde ein Branch-and-Bound-Algorithmus entwickelt, bei welchem fortschreitend Knoten an das Ende von in einer Queue gespeicherten Pfaden angehängt werden. Der Algorithmus löst das Problem exakt. Er wurde auf Probleminstanzen getestet, welche als Graphen eine Repräsentation des Straßennetzes von Baden-Württemberg hatten. Auf diesem wurden die Zeitgutschriften sowie Start- und Zielknoten uniform zufällig verteilt. Die Laufzeiten des Algorithmus wurden mit den Zeiten verglichen, welche zum Lösen des Problems mit einfachen ganzzahligen linearen Programmen benötigt wurden.

Minimizing Potential Energy in Constrained Physical Systems and Applications to Graph Drawing

  • Date: Tue, 25 Apr 2017, 13:00
  • Location: SR 301
  • Speaker: Christian Schnorr, ITI Wagner, Bachelor Thesis
  • Inhalt: Over time, physical systems converge to stable equilibrium states in which their potential energy is at a local minimum. In traditional force-directed algorithms, explicit restoring forces are used to iteratively displace the system's particles such that its implicitly defined potential energy decreases. We propose explicitly defining the system's potential energy instead, allowing for a wide range of optimization techniques to be used, and for various types of constraints to be incorporated more easily. We then demonstrate how this can be applied to drawing graphs with circular arcs. Here the constraints appear in the form of multiple incident edges being drawn using a single circular arc.

A Practical Scalable Shared-Memory Parallel Algorithm for Computing Minimum Spanning Trees

  • Date: Wed, 19 Apr 2017, 13:00
  • Location: SR 301
  • Speaker: Wei Zhou, ITI Sanders, Masters Thesis
  • Inhalt: The present thesis briefly reviews the history of the Minimum Spanning Tree (MST) Problem and a number of known algorithms to solve it. Furthermore, a new simple, elegant and practical algorithm based on Boruvka's algorithm for parallel MST computation on shared-memory machines is developed. The algorithm utilizes a parallel primitive called priority write that is easily and efficiently implementable with atomic compare-and-swap (CAS) instructions. The parallelism in the algorithm is coarse-grained and no explicit locks other than in the implementations of usual parallel primitives are needed. Experiments show that the algorithm is efficient on both synthetic and real-world graphs and is invulnerable to adversarial inputs. In our tests, it performs faster than or as fast as state-of-the-art implementations, which often perform poorly or even sequentially on particular classes of graphs. The new algorithm offers good performance even with few processors and therefore can be used as a sole universal implementation.
  • Date: Wed, 5 Apr 2017, 13:30
  • Location: SR 301
  • Speaker: Guangping Li, ITI Sanders, Bachelor Thesis
  • Inhalt: Tabucol is a local search algorithm to determine whether the vertices of an undi rected graph can be colored with k colors, such that no two vertices connected by an edge have the same color. This thesis presents an algorithm that solves the graph coloring problem with parallel Tabucol searches. A hypothesis was experimentally evaluated that sharing information among the agents will improve the performance of the parallel search. In this paper, we introduce a new matrix data structure, which counts the repeated times of one change. This statistic matrix can help recognizing long-term cycling in the local search. The sharing of this matrix among the agents can bring further improvement to our algorithm.

Massively Parallel Schizophrenic Quicksort

  • Date: Wed, 5 Apr 2017, 13:00
  • Location: SR 301
  • Speaker: Armin Wiebigke, Bachelor Thesis, ITI Sanders
  • Inhalt: Sorting algorithms for distributed memory systems are essential for quickly sorting large amounts of data. The de facto standard for communication in High Performance Computing (HPC) is the Message Passing Interface (MPI). MPI uses the concept of communicators to connect groups of PEs. Recursive algorithms may split a group of PEs into subgroups and then execute the algorithm on these subgroups recursively. A straightforward approach to implementing such an algorithm is to create a MPI subcommunicator for each subgroup. However, the time to create a MPI communicator is not negligible on a large group of PEs and may therefore drastically increase the running time of the algorithm. In this thesis, we present a communication library based on MPI that supports communicator creation in constant time and without communication. The library supports both point-to-point communication and non-blocking collective operations. We also present the first efficient im- plementation of Schizophrenic Quicksort, a recursive sorting algorithm for distributed memory systems that is based on Quicksort. Schizophrenic Quicksort guarantees perfect data balance with the drawback that some PEs have to work on two groups simultaneously. The only previous implementation scales bad on large supercomputers. We integrate our communication library into the implementation of Schizophrenic Quicksort and thus eliminate the cost for the com- municator creation almost completely. We also avoid problems caused by blocking collective operations. We also implement a better pivot selection and reduce the amount of communication in each level of recursion. Furthermore, we extend an implementation of Hypercube Quicksort with our communication library. We perform an extensive experimental evaluation of our implementations. In our experiments, our library reduces the time to create a communicator by a factor of more than 10 000 compared to MPI. In contrast, the collective operations of MPI outperformed the collective operations of our library for most inputs. On large numbers of PEs, splitting a communicator and executing the operation Broadcast 50 times (with medium inputs) with our library is still faster than a single communicator split with MPI. Our experimental results show that we improve the per- formance of Schizophrenic Quicksort by a factor of up to 40 and the performance of Hypercube Quicksort by a factor of up to 15 if we use our library instead of MPI. We compare our imple- mentation of Schizophrenic Quicksort with the implementation of Hypercube Quicksort. The results indicate that Schizophrenic Quicksort is not able to outperform Hypercube Quicksort. However, Schizophrenic Quicksort runs on any number of PEs while Hypercube Quicksort only runs on 2k PEs.

Fall 2016

Efficient computation of Harmonic Centrality on large networks: theory and practice

  • Date: Thu, 23 Mar 2017, 13:30
  • Location: SR 131
  • Speaker: Eugenio Angriman, University of Padova, Italy
  • Inhalt: In the last fifteen years a lot of progress has been made in the area of efficient algorithms for the computation of the Closeness Centrality. David Eppstein and Joseph Wang designed a fast approximation algorithm that estimates the value of the Closeness Centrality of each vertex of a network while Kazuya Okamoto, Wei Chen and Xiang-Yang Li proposed an efficient strategy to compute the exact top-/k /Closeness Centralities with high probability. Harmonic Centrality is a more recent metric and it is also well-suited for unconnected networks. However, efficient algorithms for this metric have not been developed yet. In this work we propose a revised version of the aforementioned algorithms for the Harmonic Centrality. First, we provide the fundamental theoretical background to prove time and error bounds. Then, we present the results of our Python implementation which makes use of the graph-tool as main support library. Finally, we present a brief description of a novel heuristic algorithm and its comparison with the NetworKit BFSbound function. This heuristic is based on a progressive sampling technique that exploits intermediate results for a more efficient computation of the top-/k/ Closeness Centralities.

Unpacking Planar Clustered Graphs: To Bend or Not to Bend?

  • Date: Fri, 17 Mar 2017, 14:00
  • Location: SR 301
  • Speaker: Nina Zimbel, Abschlussarbeit, ITI Wagner
  • Inhalt: Every time the layout of very big graphs shall be edited it is wise to edit an abstraction instead and then transfer the changes back to the layout of the original graph. For abstraction we use a cluster graph, in which each vertex represents one cluster of the original graph. From a planar straight-line drawing of this cluster graph we aim to construct a planar straight-line drawing of the original planar graph, which keeps the positions of the clusters and the embedding. To keep the positions of the clusters we limit the regions into which the clusters can be drawn by circles around the vertices of the cluster-graph. In contrast to some other papers in this field, which require biconnected clusters, we require connected clusters to be able to use our construction more flexible. Under the condition that the graph induced by two clusters does not contain another cluster in its interior, we show constructively that it is possible to generate a drawing of the original graph with the above-mentioned properties.

Algorithmic Methods for Stemmatological Analysis of Ancient Egyptian Literature

  • Date: Fri, 3 Mar 2017, 14:00
  • Location: SR 301
  • Speaker: Germaine Götzelmann, ITI Wagner and IPE, Bachelor Thesis
  • Inhalt: Stemmatological analysis is a standard method in disciplines of humanities to analyse text traditions. A so called stemma codicum is constructed from multiple traditioned text variants. This stemma shows genealogical relations between different copies of the same text. In the scope of Egyptologie, said method has been mainly conducted by hand in a qualitative manner. In other disciplines, methods of computer science have been used for additional quantitative analysis. In this thesis we research common methods and tools regarding their applicability on transliterations of hieroglyph texts in Egyptology. In the scope of the thesis we focus on the preprocessing steps of text regularisation and text alignment (collation). We show that the standard approach of progressive alignment is problematic with fragmentary traditioned texts. We test the potential of improvement for a supplementary iterative refinement with global alignment. Moreover, we evaluate the text alignment results on test data from the scope of Egyptology.

Using an Algorithm Portfolio to Solve Sokoban

  • Date: Wed, 22 Feb 2017, 13:00
  • Location: SR 301
  • Speaker: Nils Froleyks, ITI Sanders, Bachelor Thesis
  • Inhalt: The game of Sokoban is an interesting platform for algorithm research. It is hard for humans and computers alike. Even with its simple rules and small average level sizes there are levels that take a lot of computation for all known algorithms. In this thesis we will combine different Sokoban solvers with different domain specific enhancements into one portfolio. This portfolio can then be run in parallel on one problem until one solver finds a solution. Additionally the solvers in the portfolio can exchange data to speed up computation. We will validate the approach of algorithm portfolios for designing a parallel Sokoban solver.

Evolutionary Graph Coloring

  • Date: Wed, 22 Feb 2017, 12:30
  • Location: SR 301
  • Speaker: Marvin Williams, ITI Sanders, Bachelor Thesis
  • Inhalt: The Graph Coloring Problem (GCP) asks for the minimum number of colors required to color the vertices of a graph such that no two adjacent vertices have the same color. In this thesis we present an evolutionary algorithm for the GCP with novel crossover operations using graph partitioning. Our population contains only legal colorings and we use various greedy coloring algorithms to initialize it. In each generation, two colorings of the population function as parents. We combine them using one of the proposed crossover operations. Our first crossover uses a graph partitioning as the crossing point and generates a new coloring by selecting a different coloring for each block. The second crossover works in a similar fashion but uses a vertex separator instead of a partitioning. Our third crossover computes a new coloring from the overlap of the parents. Finally, we improve the new coloring with a local search algorithm. As the goal for our algorithm is to perform well on large graphs, we use a simple tabu search as well as fast crossovers. We evaluate our proposed algorithm by comparing it to the state-of-the-art algorithm PASS by San Segundo [36] on graph instances found in the literature. We are able to outperform PASS on almost 50% of the graph instances. [36] Pablo San Segundo. A new dsatur-based algorithm for exact vertex coloring. Comput. Oper. Res., 39(7):1724-1733, 2012.

Scalable Kernelization for the Maximum Independent Set Problem

  • Date: Wed, 22 Feb 2017, 12:00
  • Location: SR 301
  • Speaker: Demian Hespe, ITI Sanders, Masters Thesis
  • Inhalt: The NP-hard maximum independent set problem has applications in many real-world domains, such as coding theory, computer graphics, computational biology and route planning. While the problems arising from these areas are not always in the form of graphs, they can be transformed into one and then handled by an independent set algorithm independent from the domain. A technique that has been part of exact maximum independent set algorithms for a long time and recently has been discovered to be beneficial for inexact algorithms is kernelization. Kernelization is the process of reducing the size of a graph without losing the information required to compute a maximum independent set of the original graph. Algorithms for finding a kernel are much faster than algorithms for directly finding a maximum independent set. Intuitively, a kernel is the part of a graph that makes the maximum independent set problem hard. Exact branch-and-reduce algorithms find a kernel of the input graph, then branch at carefully chosen vertices and compute kernels of the new graphs after branching. Recently, finding a kernel before or during local search and evolutionary algorithms has also be found to be beneficial. In the past, extensive work has been done to lower the theoretical worst-case time complexity of finding a maximum independent set. Furthermore, there is a growing focus on algorithms that find large independent sets, but not necessarily a maximum independent set. However, very little work has been done parallelizing maximum independent set algorithms. As kernelization plays an important role in both these approaches, we develop a fast parallel algorithm for finding a relaxed version of a kernel. This relaxed kernel is sufficiently small but might still have potential to be reduced to an even smaller size by sequential algorithms. Beside parallelism we also employ a technique to prune vertices that cannot be used to further decrease the graph size at the current state of the algorithm. In this thesis we give a detailed explanation of how our kernelization algorithm works. Besides a theoretical view on the parallel application of kernelization techniques and the pruning of vertices, we also employ an extensive experimental evaluation of our implementation. Our results show that sequentially, we can find a kernel a factor of up to 4 faster than previous results and a factor of up to 11 faster using parallelism.

Communication Efficient Algorithms for Generating Massive Networks

  • Date: Wed, 22 Feb 2017, 11:30
  • Location: SR 301
  • Speaker: Sebastian Lamm, ITI Sanders, Masters Thesis
  • Inhalt: Massive complex systems are prevalent throughout all of our lives, from various biological systems as the human genome to technological networks such as Facebook or Twitter. Rapid advances in technology allow us to gather more and more data that is connected to these systems. Analyzing and extracting this huge amount of information is a crucial task for a variety of scientific disciplines. A common abstraction for handling complex systems are networks (graphs) made up of entities and their relationships. For example, we can represent wireless ad hoc networks in terms of nodes and their connections with each other. We then identify the nodes as vertices and their connections as edges between the vertices. This abstraction allows us to develop algorithms that are independent of the underlying domain. Designing algorithms for massive networks is a challenging task that requires thorough analysis and experimental evaluation. A major hurdle for this task is the scarcity of publicly available large-scale datasets. To approach this issue, we can make use of network generators. These generators allow us to produce synthetic instances that exhibit properties found in many real-world networks. In this thesis we develop a set of novel graph generators that have a focus on scalability. In particular, we cover the classic Erdos-Renyi model, random geometric graphs and random hyperbolic graphs. These models represent different real-world systems, from the aforementioned wireless ad-hoc networks to social networks. We ensure scalability by making use of pseudorandomization via hash functions and redundant computations. The resulting network generators are communication agnostic, i.e. they require no communication. This allows us to generate massive instances of up to 2^43 vertices and 2^47 edges in less than 22 minutes on 32.768 processors. In addition to proving theoretical bounds for each generator, we perform an extensive experimental evaluation. We cover both their sequential performance, as well as scaling behavior. We are able to show that our algorithms are competitive to state-of-the-art implementations found in network analysis libraries. Additionally, our generators exhibit near optimal scaling behavior for large instances. Finally, we show that pseudorandomization has little to no measurable impact on the quality of our generated instances.

Approximation Algorithms for Constrained Optimization Problems

  • Date: Fri, 27 Jan 2017, 14:00
  • Location: SR 301
  • Speaker: Dr. Joachim Spoerhase, ITI Wagner, Guest from the University of Würzburg (60 min talk)
  • Inhalt: In this talk we give an overview over some of our recent results in the area of approximation algorithms for NP-hard optimization problems. The problems under investigation have in common that they are variants of classical optimization problems that involve an additional packing or a covering constraint that renders them more difficult to approximate than the basic problem. In particular, we discuss new algorithms for location problems (capacitated k-median, knapsack median), routing problems (edge-disjoint paths), network design problems (bounded distance network design, shallow-light spanning trees), coverage problems (in a geometric setting), and submodular function maximization (with mixed packing and covering constraints). Our algorithms are based on linear programming, local search, greedy, or dynamic programming techniques. The more complex nature of the constraints involved requires for some of the mentioned problems that these constraints are violated (by a bounded factor) in order to achieve non-trivial approximability results.

Bloom Filters for ReduceBy, GroupBy and Join in Thrill

  • Date: Mon, 23 Jan 2017, 15:00
  • Location: SR 236
  • Speaker: Alexander Noe, Masters Thesis, ITI Sanders
  • Inhalt: Thrill is a prototype of a high-performance general purpose big data processing framework. In the Reduce operation, which is similar to Reduce in MapReduce, Thrill performs an all-to-all hash based data shuffle of large amounts of data. Elements only occuring on a single worker could however be reduced locally without shuffling them. To find these elements, we propose a detection algorithm based on distributed single-shot Bloom filters to efficiently detect a large portion of these elements. Additionally, we implemented an SQL-style InnerJoin operator for Thrill. For the InnerJoin operator it is not possible to perform local reduction before the hash based data shuffle. Therefore we implemented an augmented version of our detection algorithm, which detects the worker with the highest number of total occurences for each key. In order to reduce the amount of total network traffic, this worker is determined as the shuffle target for that key. We use multiple algorithmic micro-benchmarks on the AWS EC2 computing cluster to benchmark the performance of our implementations in the Thrill framework. In communication-heavy benchmarks, such as median computation and the TPC-H4 database join query, we can improve the running time by a factor of 1.5 up to 10 by using duplicate detection. In the WordCount and PageRank algorithms performed on real world data we can lower the amount of network traffic while keeping a comparable running time.

Bend Minimization of Ortho-Radial Graph Drawings

  • Date: Mon, 23 Jan 2017, 14:30
  • Location: SR 236
  • Speaker: Matthias Wolf, Masters Thesis, ITI Wagner
  • Inhalt: Es werden orthogonale Zeichnungen von 4-planaren Graphen auf Zylindern--so genannte ortho-radiale Zeichnungen--betrachtet. Ortho-radiale Beschreibungen ermöglichen es, die Form solcher Zeichnungen zu beschreiben, ohne jedoch Koordinaten oder Kantenlängen festzulegen. Für diese Beschreibungen werden außerdem Bedingungen aufgezeigt, welche sowohl notwendig als auch hinreichend für die Existenz einer Zeichnung sind. Die Fähigkeit, die Form einer Zeichnung zu beschreiben, ist ein entscheidender Schritt zur Anwendung von Tamassias Topology-Shape-Metrics-Framework auf ortho-radiales Graphenzeichnen. Zusätzlich wird gezeigt, dass es NP-vollständig ist zu entscheiden, ob ein gegebener 4-planarer Graph ohne feste Einbettung eine ortho-radiale Zeichnung ohne Kantenknicke besitzt. Beschränkt man sich jedoch auf Kaktusgraphen, so kann in Linearzeit eine knickminimale Zeichnung bestimmt werden.

Efficient Compression of Web Graphs using k^2-Trees

  • Date: Mon, 23 Jan 2017, 14:00
  • Location: SR 236
  • Speaker: Jan Broß, ITI Sanders, Masters Thesis
  • Inhalt: Web graphs are a representation of the linkage structure of the web. They represent the relationship of a certain set of URLs. Each URL in the set is represented with a node. An arc runs between two nodes u and v whenever page u contains a hyperlink to page v. Web graph compression has attracted a lot of research leading to various compression schemes exploiting typical properties of web graphs. Up to now however the time and memory needed for constructing the compressed representation was only partially addressed. We present a new construction technique based on z-order sorting for a competitive web graph representation called k^2-trees that reduces the memory consumption significantly while achieving a faster construction. Additionally we present a parallel variant of our construction technique that is an order of magnitude faster than previous work and allows processing the biggest available web graph datasets. Furthermore we present a technique to accelerate query times for hybrid k^2-trees by a factor of two compared to previous work. Thus we obtain a web graph compression method that achieves 1-4 Bits per Edge on billion node graphs while retaining query times from 2-10 microseconds.

On Smoothing Paths in Layered Graph Drawing

  • Date: Mon, 9 Jan 2017, 14:00
  • Location: SR 236
  • Speaker: Sebastian Schlund, Master's Thesis, ITI Wagner
  • Inhalt: A commonly accepted visualization style for directed acyclic graphs is a layered layout, where vertices lie on parallel vertical layers, and all edges point to the right, i.e for each directed edge (u,v), the layer of vertex u is to the left of the layer of vertex v. In this thesis we study layered layouts that incorporate additional constraints provided by a user. We concentrate on the case when the user provides a number of directed paths, with the target to be emphasized in the final drawing. In particular, we visualize all the edges of the graph as curves, and try to modify these curves such that each path forms a smooth curve. The visualization style is motivated by the perceptual Gestalt Principle of continuation, which suggests that smooth curves can be followed by the eye easier than polylines. The problem of constructing such layouts is motivated by the application in the visualization of textual variation, where the set of text variants is represented as a directed acyclic graph, so-called text-variant graph, and each sentence forms a directed path in it. The intuitive target for the visualization of text variant graphs is to make each sentence easily readable. The contribution of the thesis is a heuristic method for constructing the described visualization layout with curvy-linear edges and its experimental evaluation.

Parallel Fast Search Operations

  • Date: Fri, 16 Dec 2016, 14:30
  • Location: SR 301
  • Speaker: Yaroslav Akhremtsev, ITI Sanders, Trial Presentation for HIPC 2016
  • Inhalt: Using (a,b)-trees as an example, we show how to perform a parallel split with logarithmic latency and parallel join, bulk updates, intersection, union (or merge), and (symmetric) set difference with logarithmic latency and with information theoretically optimal work. We present both asymptotically optimal solutions and simplified versions that perform well in practice - they are several times faster than previous implementations.

Optimale zeitabhängige Pausenplanung für LKW-Fahrer mit integrierter Parkplatzwahl

  • Date: Fri, 16 Dec 2016, 14:00
  • Location: SR 301
  • Speaker: Christian Bräuer, ITI Wagner, Bachelor Thesis
  • Inhalt: LKW-Fahrer müssen in vielen Ländern Lenk- und Ruhezeiten einhalten, um Unfälle aufgrund von Übermüdung zu vermeiden. Bei der Planung einer Tour für LKW-Fahrer muss nicht nur beachtet werden, dass für eine Pause aufgrund der Fahrzeuggröße dafür vorgesehene LKW-Parkplätze nötig sind. Auch vorhersehbare Verkehrsbehinderungen wie Berufsverkehr können zu einer Verzögerung der Fahrt führen, die in einem Verstoß gegen die Lenk- und Ruhezeiten mündet. Daher wurde in dieser Arbeit ein Algorithmus entworfen, der, gegeben eine LKW-Tour und einen zeitabhängigen Straßengraphen, Pausen für den LKW-Fahrer auf Parkplätzen so einplant, dass einerseits nicht gegen die Lenk- und Ruhezeiten der EU verstoßen wird, und andererseits die Tour möglichst früh beendet werden kann.

Rectilinear Crossing Minimization

  • Date: Mon, 12 Dec 2016, 14:00
  • Location: SR 236
  • Speaker: Klara Reichard, ITI Wagner, Masters Thesis
  • Inhalt: This thesis deals with the rectilinear crossing minimization problem, which is NP-hard. More precisely, we propose a heuristic for computing a drawing of a general graph G which realizes the minimum rectilinear crossing number. Inspired by Gutwenger et al., we pursue an approach which extracts a planar subgraph that includes as many edges of G as possible and iteratively reinserts the missing edges into G. After each edge insertion nodes are moved in order to reduce the number of crossings in the current drawing. We fix the position of all nodes but one node v and move v to a position, that minimizes the number of crossings in the drawing. This position can be computed in an O((m d_max)^2) time-bound, with d_max denoting the maximum degree of a node in G. We evaluate several configurations of this algorithm, which use different strategies to avoid local optima. We compare these configurations to the spring embedder of Fruchterman and Reingold on a variety of different graph classes and observe that each of our configurations yields drawings with a significantly lower rectilinear crossing number than the commonly used spring embedder. Furthermore, our algorithm finds solutions which are close to optimal on the complete graphs K_n, for n <= 30.

Evolutionary k-way Node Separators

  • Date: Mon, 5 Dec 2016, 14:00
  • Location: SR 236
  • Speaker: Robert Williger, ITI Sanders, Bachelor Thesis
  • Inhalt: Small node separators for large graphs are used in a variety of ways, from divide-and conquer algorithms to efficient route planning algorithms. We present a new algorithm for finding small k-way node separators on connected undirected graphs. We use an evolutionary algorithm to combine different separators in order to generate improved offsprings with locally good parts of both parent separators. Additionally, we also propose a new k-way local search to further improve already existing separators. Our experimental evaluation of our algorithm shows that we have an average improvement of 18% and 23% respectively for our two different configurations and a maximum improvement of 64% compared to the already existing algorithm in KaHIP for finding k-way node separators.

Beschleunigung maximaler Flüsse durch elektrische Flüsse

  • Date: Fri, 2 Dec 2016, 15:00
  • Location: SR 301
  • Speaker: Christoph Hess, PARCO (Bachelor Thesis)
  • Inhalt: To appear.

Observability of Multi-domain Energy Distribution Networks

  • Date: Fri, 2 Dec 2016, 14:30
  • Location: SR 301
  • Speaker: Carina Mieth, Short Presentation: IRS Hohmann and ITI Wagner, Masters Thesis
  • Inhalt: Due to fundamental changes in the current power supply systems, the existing central power supply with separated physical domains transforms to a decentralized cross-domain supply structure. Important components of this development are renewable energies, combined heat and power (CHP), energy storages and power-to-X technologies. The corresponding systems operate mostly on the distribution network level and cause time-varying power flows, which are not detectable for the network operator because of an insufficient sensor equipment and experienced-based---but not optimal---placement. As a result, there are impermissible limit violations, e.g., the voltage or pressure in the electrical or gas network, respectively. The placement of sensors to obtain an observable multi-domain energy distribution network is just one arising question in this research field.
  • Date: Mon, 21 Nov 2016, 14:00
  • Location: SR 236
  • Speaker: Kai Fieger, ITI Sanders, Bachelor Thesis
  • Inhalt: This thesis presents an optimal algorithm that solves the longest path problem for undirected graphs. The algorithm makes use of graph partitioning and dynamic programming. It’s performance was evaluated in a number of benchmarks and compared to other known algorithms. The runtime of the algorithm was shown to be significantly faster on the tested graphs.

Graph Drawing Aesthetics: The impact of shapes on the first impression

  • Date: Fri, 18 Nov 2016, 14:00
  • Location: SR 301
  • Speaker: Hannes Wächter, ITI Wagner, Diploma Thesis
  • Inhalt: We investigated the impact of shapes on the first impression of graph drawings from an aesthetic perspective. Particularly we examined if curvature and complexity of the outline of a graph visualization influences the perceived beauty and interest. To understand whether the perception of shapes significantly differs from the perception of graphs, using those shapes as outlines, we performed an experiment for both pure shapes and graphs. To capture the first impression we present the stimuli for 100 ms only. We repeat the questionnaire using unlimited time presentation. Indeed, we could show that there are relations between curvature and beauty as well as between complexity and interest. These relations are observable both after 100ms and unlimited time presentation and some of them are clearer for graph drawings than for pure shapes.

A Parallel Subgraph Isomorphism Algorithm

  • Date: Tue, 15 Nov 2016, 14:00
  • Location: SR 010
  • Speaker: Raphael Kimmig, PARCO (Diploma Thesis)
  • Inhalt: The subgraph isomorphism problem is the problem of finding a smaller pattern graph in a larger target graph, or more formally finding an injection from the nodes of the pattern graph to the nodes of the target graphs such that the edges of the pattern graph are preserved. It is NP-complete and has applications in many areas including biology and chemistry. One of the fastest algorithms for solving this problem is RI. We present a CPU parallelization of RI and RI-DS (a variant of RI for dense graphs) based on work stealing. Our implementation demonstrates that significant speedup can be achieved on real world biochemical datasets (up to 9.2 with 16 cores). We also present an improved version of RI-DS called RI-DS-SI-FC. Thanks to improved search space reduction it achieves slightly shorter runtimes on the studied datasets, compared to the already highly-tuned RI-DS.

Algorithmen für Straßenbeschriftung dynamischer Karten diskreter und kontinuierlicher Maßstäbe

  • Date: Fri, 11 Nov 2016, 14:00
  • Location: SR 301
  • Speaker: Alexander Gellner, Bachelor Thesis, ITI Wagner
  • Inhalt: Mit der zunehmenden Digitalisierung von Landkarten ist die Kartographie in den letzten Jahren immer mehr ins Aufgabengebiet der Informatik gerückt, in welcher an Algorithmen zur automatischen Beschriftung von Karten geforscht wird. Diese Arbeit befasst sich speziell mit dynamischen Straßenkarten, welche es dem Benutzer erlauben, Straßennetzwerke in verschiedenen Maßstäben zu betrachten. Dabei werden sowohl Straßenkarten diskreter als auch kontinuierlicher Maßstäbe in Betracht gezogen. Für diese werden Beschriftungen gesucht, welche einen fließenden Übergang zwischen den einzelnen Maßstäben ermöglichen und zugleich über einen hohen Informationsgehalt verfügen.

Algorithm Engineering for the calculation of connected components in threedimensional binary images

  • Date: Tue, 8 Nov 2016, 09:00
  • Location: R 211
  • Speaker: Yvonne Braun, ITI Sanders, Masters Thesis
  • Inhalt: Diese Arbeit beschäftigt sich mit der Berechnung von Zusammenhangskomponenten in 3D - Binärbildern. Das Problem ist für den 2D Fall bereits gut untersucht. Der Inhalt dieser Arbeit war bereits existierende Ansätze für den auf den 3D Fall zu übertragen. Speziell wurde betrachtet inwiefern existierende Verfahren parallelisiert werden können. Die Arbeit beschäftigt sich vor allem mit Graphenalgorithmen und deren Parallelisierung.Speziell wurde betrachtet welche Datenstrukturen sich gut für das speichern und den schnellen Zugriff auf die Bilddaten eignen.

Stacked Treewidth and the Colin de Verdiére Number

  • Date: Fri, 4 Nov 2016, 14:00
  • Location: SR 301
  • Speaker: Lasse Wulff, ITI Wagner, Bachelor Thesis
  • Inhalt: Für jede natürliche Zahl k entsteht ein sogenannter k-tree, indem man mit einer (k+1)-Clique beginnt und wiederholt einen neuen Knoten vollständig mit einer existierenden k-Clique verbindet. Wir nennen einen k-tree einen stacked k-tree, wenn während dieses Prozesses keine k-Clique doppelt ausgewählt wird. Ferner bezeichne die stacked treewidth stw(G) eines Graphen G die kleinste Zahl k, sodass G Teilgraph eines stacked k-trees ist. Die Colin de Verdière number µ(G) eines Graphen G ist ein 1993 von Yves Colin de Verdière eingeführter, spektraler Graphenparameter mit der überrraschenden Eigenschaft, dass die außerplanaren, planaren, bzw. linklessly embeddable Graphen gerade durch µ(G) <= 2, µ(G) <= 3, bzw. µ(G) <= 4 charakterisiert werden. Dieser Vortrag behandelt die Resultate unserer Untersuchung des Zusammenhangs zwischen stw(G) und µ(G). Wir führen die nötigen Begriffe ein und zeigen, dass es einerseits nichttriviale Gemeinsamkeiten zwischen µ(G) und stw(G) gibt, dass aber andererseits an einigen Stellen der erwartete und der tatsächliche Zusammenhang nicht übereinstimmen.

On Threshold Editing

  • Date: Mon, 31 Oct 2016, 14:00
  • Location: SR 236
  • Speaker: Matthias Schimek, Bachelorarbeitsvortrag, ITI Wagner
  • Inhalt: In dieser Arbeit werden die Probleme Threshold Deletion und Threshold Editing auf Quasi-Threshold-Graphen untersucht. Das Problem Threshold Deletion besteht darin, eine minimale Anzahl von Kanten des Eingabegraphen zu löschen, um diesen in einen Threshold-Graphen umzuwandeln. Für Threshold Editing dürfen nicht nur Kanten gelöscht, sondern auch Kanten hinzugefügt werden, um den Eingabegraphen in einen Threshold-Graphen zu überführen. Threshold-Graphen können durch verbotene Subgraphen charakterisiert werden. Es sind genau die Graphen, welche keinen P4, C4 oder 2K2 als knoteninduzierten Subgraphen enthalten. Auf allgemeinen Graphen sind beide Probleme NP-vollständig. Als Eingabegraphen werden in dieser Arbeit nur Quasi-Threshold-Graphen betrachtet. Diese sind Graphen, die keinen P4 oder C4 als knoteninduzierten Subgraphen enthalten. Für Threshold Deletion wird ein Algorithmus vorgestellt, der das Problem in O(|V| + |E|) löst, wobei Q = (V,E) der Eingabegraph ist. Ebenso wird ein Algorithmus für das Problem Threshold Editing gegeben, dieser hat eine exponentielle Laufzeit in der Knotenanzahl des Eingabegraphen. Jedoch erweist sich der Algorithmus auf den zur Evaluation verwendeten zufällig generierten Graphen mit bis zu 300 Knoten als praktikabel. Weiterhin wird eine Heuristik für dieses Problem vorgestellt, deren Laufzeit quadratisch ist.

Parallel Bulk-Loading and Structural Improvement for the PH-Tree

  • Date: Fri, 28 Oct 2016, 14:00
  • Location: SR 301
  • Speaker: Maximilian Czerny, Masterarbeitsvortrag, ITI Sanders
  • Inhalt: Many modern applications rely on e fficient multidimensional access methods. From geographic simulations to brain models, huge datasets need to be indexed and processed. This thesis builds on the Patricia-Hypercube-tree, a space efficient multidimensional index that has increasingly outperformed other access methods for big datasets. A restructured low-level implementation is provided to exploit manual memory management. As a result the insertions are about 2x faster compared to the available implementation suff ering from garbage collection. The fundamental representation of data is changed to a bit interleaved format allowing fast operations even on high-dimensional objects. To effi ciently index datasets resident in main memory novel techniques for both sequential and parallel bulk-loading are discussed. The data coherency is exploited to forecast the size of inner nodes and to skip entire levels of the tree hierarchy thereby allowing threads to avoid contention when building in parallel. The combination of these approaches yields linear scalability in the experiments on neuronal spatial data. Thus, the frst parallel bulk-loading approach for any multidimensional index assuming a shared memory architecture is proposed.

Umlegeverfahren für öffentliche Verkehrsnetze mittels minimal erwarteter Ankunftszeit

  • Date: Fri, 14 Oct 2016, 14:00
  • Location: R -102
  • Speaker: Holger Ebhart, ITI Wagner, Bachelor Thesis
  • Inhalt: Als Verkehrsplaner stellt man sich oft die Frage: Wie viele Personen fahren in welchem Zug? Diese Frage möchte man für eine gegebene Nachfrage und einen Fahrplan lösen. In dieser Arbeit wird dafür ein neuer Algorithmus vorgestellt. Dieser löst das Problem mit einer kürzeren Laufzeit als bisher. Um die Eingabe zu konstruieren modellieren wir zuerst ein öffentliches Personen-Verkehrsnetzwerk. Außerdem benötigen wir noch ein Nachfrage-Modell. Der Algorithmus nimmt diese beiden Eingaben und führt darauf eine Simulation durch. Dabei werden einzelne Fahrgäste durch das Netzwerk zu ihrem Ziel geroutet. Als Grundlage dafür dient die minimal erwartete Ankunftszeit. Der präsentierte Algorithmus zeigt als Ergebnis welcher Fahrgast welchen Zug benutzt. Im Vergleich zu schon verfügbaren Tools konnten wir die Laufzeit einer Umlegung verbessern.

Entwicklung eines Algorithmus für individuelle Reiseplanung in der mobilen Sehenswürdigkeitenführung

  • Date: Tue, 4 Oct 2016, 13:00
  • Location: SR 236
  • Speaker: Anastasia Osintseva, Masterarbeitsvortrag, ITI Sanders
  • Inhalt: In dieser Masterthesis wurden drei Varianten des Route-Planers, als zentrale Komponente eines Algorithmus für individuelle Reiseplanung entworfen, implementiert und evaluiert. Die Variante mGreedy basiert dabei auf dem Greedy Algorithmus, die Varianten mDGA und aDGA basieren auf den verteilten Genetischen Algorithmen. Die Abschlussarbeit setzt sich aus drei Hauptteilen zusammen. So werden im Kapitel 2 die theoretischen Fragen in Bezug auf die kombinatorischen Optimierungsprobleme und die Algorithmen, die zur Lösung kombinatorischer Optimierungsprobleme verwendet werden, geklärt. Im Kapitel 3 werden die entworfenen Algorithmen behandelt und im Kapitel 4 werden diese Algorithmen evaluiert. Die Evaluierung der entworfenen Algorithmen hat gezeigt, dass der erweiterte verteilte genetische Algorithmus - aDGA, der eine Erweiterung des mDGA-Algorithmus ist, insgesamt die besten Resultate liefert. Die Qualität der Lösungen sowie die Laufzeit des Algorithmus kann durch die Verwendung von geeigneten Operatoren und Parametern gesteuert werden. Es hat sich außerdem herausgestellt, dass die verwendete Programmiersprache Java nur bedingt für die Implementierung derartigen hochgradig nebenläufigen Algorithmen geeignet ist. Falls die in dieser Abschlussarbeit entworfenen Algorithmen in einer Programmiersprache, die für solche Aufgaben besser geeignet sind, implementiert werden (Erlang, Golang), ist zu erwarten, dass die Evaluierung der Ergebnisse zu besseren Ergebnissen (besonders in der Laufzeit) führt.

Spring 2016

Applying maxent-stress graph drawing to protein structure determination

  • Date: Thu, 29 Sep 2016, 10:30
  • Location: SR 010
  • Speaker: Michael Wegner, PARCO (Masters Thesis)
  • Inhalt: Distance geometry problems arise in a rich set of real-world appli- cations. One of the most prominent applications appears in biology where we want to compute the three-dimensional structure of a protein based on a sparse set of distances obtained by experimen- tal measurements. Knowing the structure of a protein is of great importance as it is key to understanding its functions and properties. Many existing algorithms exist for this problem but most of them require either too much time or have other major restrictions that make them difficult to use. In this thesis we want to make use of the close relation between distance geometry problems and graph drawing by implementing and extending a graph drawing algorithm recently proposed by Gansner et al. to handle distance geometry problems. Our algorithm works for arbitrary dimensions and is suitable for most distance geometry problems. We test the performance of our algorithm in the setting of protein structure determination. We are able to compute protein structures of good quality in a matter of seconds, outperforming publicly available competitors both in terms of quality and runtime on most of our instances. On average, our algorithm produces 18% lower rmsd values than the best tested competitor and is more than 15 times faster than this competitor. Our algorithm also supports the input of a probability for each given distance interval, stating how probable it is that the actual distance lies in the interval. This additional input is often available from experimental measurements and to our knowledge, our algorithm is the first to support this new problem.

Generating massive complex networks with hyperbolic geometry faster in practice (Probevortrag HPEC)

  • Date: Tue, 6 Sep 2016, 13:00
  • Location: SR 301
  • Speaker: Moritz von Looz-Corswarem, PARCO
  • Inhalt: Generative network models play an important role in algorithm development, scaling studies, network analysis, and realistic system benchmarks for graph data sets. The commonly used graph-based benchmark model R-MAT has some drawbacks concerning realism and the scaling behavior of network properties. A complex network model gaining considerable popularity builds random hyperbolic graphs, generated by distributing points within a disk in the hyperbolic plane and then adding edges between points whose hyperbolic distance is below a threshold. We present a fast generation algorithm for such graphs. Our experiments show that our new generator achieves speedup factors of 3-60 over the best previous implementation. One billion edges can now be generated in under one minute on a shared-memory workstation. Furthermore, we present a dynamic extension to model gradual network change, while preserving at each step the point position probabilities.

Querying Probabilistic Neighborhoods in Spatial Data Sets Efficiently

  • Date: Fri, 12 Aug 2016, 14:00
  • Location: SR 301
  • Speaker: Moritz von Looz-Corswarem, Parco
  • Inhalt: The probability that two spatial objects establish some kind of mutual connection often depends on their proximity. To formalize this concept, we define the notion of a emph{probabilistic neighborhood}: Let $P$ be a set of $n$ points in $mathbb{R}^d$, $q in mathbb{R}^d$ a query point, $dist$ a distance metric, and $f : mathbb{R}^+ ightarrow [0,1]$ a monotonically decreasing function. Then, the probabilistic neighborhood $N(q, f)$ of $q$ with respect to $f$ is a random subset of $P$ and each point $p in P$ belongs to $N(q,f)$ with probability $f(dist(p,q))$. Possible applications include query sampling and the simulation of probabilistic spreading phenomena, as well as other scenarios where the probability of a connection between two entities decreases with their distance. We present a fast, sublinear-time query algorithm to sample probabilistic neighborhoods from planar point sets. For certain distributions of planar $P$, we prove that our algorithm answers a query in $O((|N(q,f)| + sqrt{n})log n)$ time with high probability. In experiments this yields a speedup over pairwise distance probing of at least one order of magnitude, even for rather small data sets with $n=10^5$ and also for other point distributions not covered by the theoretical results.

Computational Complexity of Energy Network Problems

  • Date: Mon, 8 Aug 2016, 14:00
  • Location: SR 236
  • Speaker: Karsten Lehmann, ITI Wagner, Guest from NICTA Energy Systems Research Group and the Optimization Research Group
  • Inhalt: In the study of energy networks, an important question has been whether practical network problems can be efficiently approximated. In energy network analysis, there are three key problems. Power Flow models the current state of the energy network; Optimal Power Flow additionally includes an objective function representing power generation cost (which may vary from generator to generator); and, Maximum Power Flow models the generation dispatch that satisfies the most demand possible in a fixed network. In this talk, we present an overview of the computational complexity of these problems in the context of different modelling assumptions, such as Alternating Current (AC), Lossless-Sin AC Approximation, and Linear AC Approximation with line switching.

Selfish Agents on Capacity-Restricted Resources - When There is Not Enough Room for Everyone

  • Date: Tue, 2 Aug 2016, 14:00
  • Location: SR 301
  • Speaker: Max Drees, ITI Wagner, Guest from Heinz Nixdorf Institut Universität Paderborn
  • Inhalt: The field of game theory deals with systems (or games) of multiple participants (called players) who interact with each other. Every player only decides on his own behavior (his strategy), but the individual outcome he experiences also depends on the strategies of the other players. In the model of budget games, players compete over resources with finite budgets. As a strategy, a player chooses one of finitely many demand vectors, which impose a non-negative demand on each resource. If the total demand by all players at a single resource does not exceed its budget, the utility each player gains from that resource equals his demand for it. Otherwise, the budget is split between the players proportionally to their demands. The total utility of a player is then defined as the sum of the utilities gained from all resources. In this talk, we focus on pure Nash equilibria (NE) in budget games. A pure NE is a state in which no player can further increase his own utility through a unilateral strategy change. In general, these do not exist in budget games. Therefore, we take a closer look at approximate pure NE and give both upper and lower bounds for their existence. We also introduce an algorithm to compute approximate pure NE efficiently for games in which the total demands of the individual players do not deviate too much from each other.

Advancing Algorithms and Methodology for Exploratory Network Analysis

  • Date: Fri, 15 Jul 2016, 13:30
  • Location: SR 301
  • Speaker: Maximilian Vogel, PARCO (Masters Thesis)
  • Inhalt: The neighborhood function which yields for a natural number t the amount of node pairs that can be connected in up to t hops, receives little attention although some distance related measures like the effective diameter can be derived from it. This may be due to the high asymptotic running of O(n(n + m)) for unweighted graphs. In this thesis an approximation algorithm from the literature[17] as well as a heuristic based on the breadth-first search and sampling are implemented and experimentally evaluated with regards to processing rate and accuracy. Climate networks[21] are a new approach to model and analyze the global climate as a dynamic system. The methodology borrows classic network analytic measures. Beyond that sophisticated approaches[13] targeting the extraction of dipoles (stationary, opposed air pressure systems) such as the North Atlantic oscillation (NAO) have been introduced. In this thesis the methodology behind the climate networks is discussed and an exploratory analysis regarding the NAO is conducted. Furthermore, two of the more recent approaches are implemented and applied with the goal to find the NAO.

Optimierung der taktischen Transportplanung unter Berücksichtigung von Transportkapazität und Auftragszeitfenster

  • Date: Mon, 11 Jul 2016, 13:00
  • Location: SR 301
  • Speaker: Moritz Heipe, ITI Sanders, Masters Thesis

Probevortrag zur Verteidigung

  • Date: Mon, 20 Jun 2016, 13:00
  • Location: SR 301
  • Speaker: Christian Staudt, PARCO
  • Inhalt: Geplant sind 25 Minuten Talk, dann Kritik (open end, kommen/gehen individuell)

Probevortrag zur Verteidigung

  • Date: Fri, 17 Jun 2016, 14:00
  • Location: SR 301
  • Speaker: Christian Staudt, PARCO
  • Inhalt: Geplant sind 25 Minuten Talk, dann Kritik (open end, kommen/gehen individuell)

Optimization Models for Flood Mitigation

  • Date: Tue, 14 Jun 2016, 10:00
  • Location: SR 010
  • Speaker: Alberto Giudici, U Milano, PARCO
  • Inhalt: This talk deals with different combinatorial optimization models for the problem of mitigating the damage caused to buildings by a flood. The general setting is that of an arc deletion problem: in a directed graph with arc weights and node costs, one has to remove a subset of arcs in order to minimize the total cost of the nodes that are reachable, after the arc removal, from some prespecified nodes. For those problems, complexity results are obtained and algorithms for solving them to optimality are developed.

Simultaneous Representation of Proper Interval Graphs

  • Date: Fri, 10 Jun 2016, 14:45
  • Location: SR 301
  • Speaker: Michael Vollmer, Masters Thesis, ITI Wagner
  • Inhalt: In this work we study the simultaneous representation of proper interval graphs. While we show that the problem is NP-complete in general, we also present a linear-time recognition algorithm for simultaneous proper interval graphs with sunflower intersection, that is, all graphs share the same subgraph. The recognition algorithm is based on the concept that we can separate a simultaneous proper interval graphs into smaller graphs, which we can verify in an easier manner, such that no solutions are lost. These algorithms and the tools used are based on a new characterization of proper interval graphs using clique orderings instead of vertex orderings.

Extending Partial Planar Drawings of Level Graphs

  • Date: Fri, 10 Jun 2016, 14:15
  • Location: SR 301
  • Speaker: Guido Brückner, Masters Thesis, ITI Wagner
  • Inhalt: Level graphs are directed graphs where vertices are immutably assigned to discrete levels and all edges point downwards. A level graph is planar if it admits a drawing where all edges are drawn as y-monotone curves and no two edges cross each other. Di Battista and Nardelli and Jünger et al. showed that recognizing planar level graphs is possible in linear time. Jünger and Leipert extended their approach to show that finding a planar drawing of planar level graphs is feasible in linear time as well. A partial planar drawing of a level graph G is a planar drawing <' of a subgraph G' of G. This work asks, and answers, the question whether a given partial planar drawing <' can be extended to a planar drawing < of the entire graph. The first result is that extending partial planar drawings of level graphs with a single source is possible in polynomial time. This is shown on the basis of an algorithm extending the approach of Di Battista and Nardelli, which heavily relies on the PQ-tree data structure, by the concept of an order graph. The result is then improved by merging the PQ-tree and the order graph data structure into a new data structure, the constrained PQ-tree. The domain of this single-source algorithm can be trivially broadened to include all graph families with a constant number of sources. The second result is that extending partial planar drawings of level graphs with multiple sources is NP-complete in general. To this end, two Karp reductions, one from 3-Partition and one from Planar Monotone 3-Sat, are presented. These two reductions lead to graph families with differing properties, allowing for insights into where the complexity of the problem stems from, and which approaches to find efficient algorithms for certain subclasses of level graphs are unlikely to be met by success.

Local Community Detection for Global Overlapping Community Detection

  • Date: Fri, 10 Jun 2016, 13:45
  • Location: SR 301
  • Speaker: Eike Röhrs, Masterarbeitsvortrag, ITI Wagner
  • Inhalt: We present two novel Local Community Detection (LCD) algorithms. They are based on scoring vertices based on the number of triangles that their incident edges are part of, which leads to good results on synthetic benchmark graphs and real world networks. Additionally, we use a scheme of Lancichinetti et al. [1] to turn our and other LCD algorithms into Global Overlapping Community Detection (GOCD) algorithms. We build on top of this scheme with our LCD algorithms and expand it with the ability to detect communities that are nearly duplicates. Moreover, we look at the performance of this scheme with different LCD algorithms and compare them to algorithms that are specifically designed for the task of GOCD. Our LCD algorithms produce the best results in our experiments on synthetic benchmark graphs and yield good results on graphs from a set of 100 Facebook networks. Our GOCD algorithms also detect quite good communities and are the best of all GOCD algorithms that use the scheme of Lancichinetti et al. [1] Andrea Lancichinetti, Santo Fortunato, and János Kertész. Detecting the overlapping and hierarchical community structure in complex networks

Outlier Detection for Modularity-based Clustering

  • Date: Tue, 7 Jun 2016, 13:00
  • Location: SR 301
  • Speaker: Fabian Hentschel, Bachelorarbeit, ITI Wagner
  • Inhalt: Das Clustern von Graphen zu einer Partition ist eine häufig genutzte Technik, um Informationen über Substrukturen innerhalb des Netzwerks zu erhalten. Diese Substrukturen werden als Communities bezeichnet. Es lassen sich jedoch nicht immer alle Knoten eines Graphen einfach in Communities zuordnen. Knoten, die sich nur sehr schwierig in die existierende Communitystruktur einfügen, heißen Ausreißer. Als Definition für Ausreißer wird Vergleich der Modularity verschiedener Partitionen herangezogen. Im Anschluss daran werden Hypothesen entwickelt, wie Ausreißer schnell identifiziert werden können. Diese Hypthesen basieren auf den Zentralitätsmaßen Betweenness und Closeness, sowie auf dem Zählen von Drei- und Vierecken innerhalb des Graphen und außerdem auf der Vorhersage einer Partition für den Vergleich gemäß der Definition für Ausreißer. Die Hypothesen überprüfen wir mit Experimenten auf zufällige generierten Graphen und auf Netzwerken basierend auf echten Daten. Diese experimentelle Überprüfung zeigt, dass nur unsere Methode, die auf der Vorhersage einer Partition beruht, bestand hat und für die schnelle Identifikation von Ausreißern geeignet ist.

Better partitions of protein graphs for subsystem density-functional theory

  • Date: Fri, 3 Jun 2016, 14:00
  • Location: SR 301
  • Speaker: Moritz von Looz-Corswarem, Probevortrag für SEA, PARCO
  • Inhalt: Determining the interaction strength between proteins and small molecules is key to analyzing their biological function. Quantum-mechanical calculations such as Density Functional Theory (DFT) give accurate and theoretically well-founded results. With common implementations the running time of DFT calculations increases quadratically with molecule size. Thus, numerous subsystem-based approaches have been developed to accelerate quantum-chemical calculations. These approaches partition the protein into different fragments, which are treated separately. Interactions between different fragments are approximated and introduce inaccuracies in the calculated interaction energies. To minimize these inaccuracies, we represent the amino acids and their interactions as a weighted graph in order to apply graph partitioning. None of the existing graph partitioning work can be directly used, though, due to the unique constraints in partitioning such protein graphs. We therefore present and evaluate several algorithms, partially building upon established concepts, but adapted to handle the new constraints. For the special case of partitioning a protein along the main chain, we also present an efficient dynamic programming algorithm that yields provably optimal results. In the general scenario our algorithms usually improve the previous approach significantly and take at most a few seconds.

Accelerating Local Search for the Maximum Independent Set Problem

  • Date: Tue, 31 May 2016, 13:30
  • Location: SR 301
  • Speaker: Sebastian Lamm, SEA trial talk, ITI Sanders
  • Inhalt: Computing high-quality independent sets quickly is an important problem in combinatorial optimization. Several recent algorithms have shown that kernelization techniques can be used to find exact maximum independent sets in medium-sized sparse graphs, as well as high-quality independent sets in huge sparse graphs that are intractable for exact (exponential-time) algorithms. However, a major drawback of these algorithms is that they require significant preprocessing overhead, and therefore cannot be used to find a high-quality independent set quickly. In this paper, we show that performing simple kernelization techniques in an online fashion significantly boosts the performance of local search, and is much faster than pre-computing a kernel using advanced techniques. In addition, we show that cutting high-degree vertices can boost local search performance even further, especially on huge (sparse) complex networks. Our experiments show that we can drastically speed up the computation of large independent sets compared to other state-of-the-art algorithms, while also producing results that are very close to the best known solutions.

Simulated Annealing-Based Heuristics for Wind Farm Cabling Problems

  • Date: Tue, 31 May 2016, 13:00
  • Location: SR 301
  • Speaker: Sebastian Lehmann, Masters Thesis, ITI Wagner
  • Inhalt: In a wind farm, the cables connecting turbines and substations with the power grid significantly contribute to its installation cost. Minimizing the cabling cost traces back to a capacitated network flow problem similar to those arising in areas such as logistics and transport. In this work, we study the following cable layout problem: In the wind farm, the locations of turbines and substations are fixed, and they should be connected with cables. We are given a set of cable types, which differ in their cost per meter and in the amount of power they support. We are interested in the cable network minimizing the cabling cost, such that the farm is connected properly. We formally model this problem as a capacitated minimum-cost flow problem with non-convex edge cost functions. This problem is NP-hard which means that, as matters stand, no polynomial time algorithm is known. We also model the cable layout problem as a mixed integer linear program (MILP) which can be solved using a generic optimizer. As an alternative, we propose a heuristic based on Simulated Annealing, which we qualitatively compare with the MILP solved with Gurobi Optimizer, a generic optimization program. In our experiments, it turns out that our heuristic is a good alternative to the MILP model for small and medium-sized instances. For wind farms with up to 450 turbines, our solution outperforms the results of Gurobi in the majority of cases. We propose different modifications to our heuristic, of which only some were useful to achieve these results. We conclude the work with different additional ideas for improvements which could be tried to make the heuristic suitable for even larger wind farms.

Measuring Search Effectiveness: Bringing the User Back

  • Date: Tue, 24 May 2016, 11:30
  • Location: SR 301
  • Speaker: Dr. Falk Scholer, Royal Melbourne Institute of Technology, Australia
  • Inhalt: As computer scientists, many of the systems and applications that we build are ultimately intended to be used by people to complete real world tasks. However, the experimental evaluation of what makes a system "good" can be difficult, and is sometimes not related to the end user. This talk will examine the effectiveness measurement of information retrieval systems, and demonstrate that the main evaluation methodology, using test collections, can lead to conclusions that don't match task-based outcomes of end users. I will then present recent work that investigates the issue of relevance perceptions and the technique of magnitude estimation, an approach from the field of psychophysics that aims to directly measure subjective user experiences. Speaker Bio: Dr Falk Scholer is an Associate Professor at RMIT University in Melbourne, Australia. He is an active researcher in the field of information retrieval (IR), where his key interests include: the evaluation of search systems; relevance and user perceptions; interactive search and user modelling; document summarisation; and efficient indexing

Communication Efficient Algorithms for Top-k Selection Problems

  • Date: Fri, 13 May 2016, 09:15
  • Location: SR 236
  • Speaker: Lorenz Hübschle-Schneider, Probevortrag für IPDPS, ITI Sanders
  • Inhalt: We present scalable parallel algorithms with sublinear per-processor communication volume and low latency for several fundamental problems related to finding the most relevant elements in a set, for various notions of relevance: We begin with the classical selection problem with unsorted input. We present generalizations with sorted inputs, dynamic content (bulk-parallel priority queues), and multiple criteria. Then we move on to finding frequent objects and top-k sum aggregation.

Fast Maximization of Betweenness and Closeness of a Node

  • Date: Tue, 10 May 2016, 13:30
  • Location: SR 301
  • Speaker: Dominik Kiefer, ITI Meyerhenke, Abschlussarbeit

Semi-externes Clustern von Graphen mit der Louvain-Methode

  • Date: Tue, 10 May 2016, 13:00
  • Location: SR 301
  • Speaker: Oliver Plate, Bachelorarbeit, ITI Wagner
  • Inhalt: Im Kontext dieser Arbeit wird das Clustern von Netzwerken betrachtet. Ziel ist dabei, Netzwerke so in Cluster zu zerlegen, dass die Knoten innerhalb der Cluster möglichst viele Verbindungen untereinander aufweisen. Zur Findung solcher Clusterungen auf Graphen gibt es viele verschiedene Ansätze und Algorithmen, hier wird die Louvain-Methode von Blondel et al. betrachtet. Die meisten Algorithmen behalten bei ihren Berechnungen alle relevanten Daten, wie zum Beispiel die verschiedenen Knoten und Kanten eines Graphen, im internen Speicher. Mit der rasant zunehmende Größe von sozialen Netzwerken oder Netzwerken, die aus dem World Wide Web generiert werden, müssen aber immer größere Graphen untersucht werden. Diese weisen oft mehrere Milliarden Knoten und Kanten auf, sodass den internen Verfahren durch den verfügbaren Hauptspeicher Grenzen gesetzt sind. In dieser Arbeit wird untersucht, inwiefern die Louvain-Methode auch die Auslagerung von Daten auf externe Speicher (Festplatten) zulässt, sodass ohne Vergrößerung des Hauptspeicher auch die Clusterung großer Graphen durchgeführt werden kann. Es dazu zwei verschiedene Ansätze vorgestellt und experimentell evaluiert.

Improving a Hierarchical Evolutionary Algorithm with Applications in Optimization and Machine Learning

  • Date: Fri, 29 Apr 2016, 14:30
  • Location: SR 301
  • Speaker: Michael Neumann, Diplomarbeit, PARCO


  • Date: Fri, 29 Apr 2016, 14:00
  • Location: SR 301
  • Speaker: Daniel Ferizovic, Bachelorarbeit, ITI Sanders

Experimental Evaluation of a Divide&Conquer-Based Algorithm for Bend Minimization in Planar Orthogonal Drawings

  • Date: Fri, 22 Apr 2016, 15:30
  • Location: SR 301
  • Speaker: Tobias Stocker, Bachelorarbeit, ITI Wagner
  • Inhalt: Knickminimierung ist das algorithmische Problem, die Anzahl der Knicke in einer orthogonalen planaren Zeichnung eines planaren Graphen zu minimieren. Das Ziel dieser Minimierung der Knicke ist es, das Aussehen und die Lesbarkeit dieser Graphen zu verbessern. Während das Problem im Allgemeinen NP-vollständig ist, ist es für plane Graphen - planare Graphen mit fester Einbettung - in Polynomialzeit lösbar. Diese Arbeit konzentriert sich auf einen bestimmten Algorithmus für das Knickminimierungsproblem eines planen Graphen, welcher das Problem durch ein Flussproblem mit minimalen Kosten modelliert und es mit Hilfe des Konzeptes von "teile und herrsche" rekursiv löst. Wir präsentieren eine Implementation dieses rekursiven Algorithmus, der das Problem eines Flusses mit minimalen Kosten löst, und evaluieren den Algorithmus in der Praxis basierend auf dieser Implementation. Aufgrund der Tatsache, dass der rekursive Algorithmus in der Theorie eine bessere Laufzeit hat als vorherige Algorithmen für das Flussproblem mit minimalen Kosten, wollen wir die Laufzeiten dieser Algorithmen vergleichen. Wir kamen zu dem Ergebnis, dass der rekursive Algorithmus auch in der Praxis schneller ist, zumindest für größere Graphen mit mehr als 90.000 Knoten.

Algorithms for crossing minimisation in book drawings

  • Date: Fri, 22 Apr 2016, 15:00
  • Location: SR 301
  • Speaker: Jonathan Klawitter, Masterarbeit, ITI Wagner
  • Inhalt: A book with k pages consists of a line (the spine) and k half-planes (the pages), each with the spine as boundary. In a k-page book drawing of a graph the vertices lie on the spine, and each edge is drawn as arc in one page. The minimal number of edge crossings in a k-page book drawing of a graph is called its k-page crossing number, which, in general, is NP-hard to determine [BE14]. A book drawing can be described by an order of the vertices on the spine and a distribution of the edges to pages. To compute book drawings, we combine vertex order heuristics with edge distribution heuristics and create heuristics that compute both simultaneously. We experimentally evaluate the performance of these heuristics on a new test suite that is centered on different graph classes. It turns out that our new heuristics produce drawings with fewer crossings for most of the tested graphs. We further investigate the optimisation of book drawings with force-based approaches, greedy and evolutionary algorithms as well as the successful combinations of the latter two.

Zeitabhängige energieoptimale Routen für Elektrofahrzeuge

  • Date: Fri, 22 Apr 2016, 14:30
  • Location: SR 301
  • Speaker: Oliver Thal, Bachelorarbeit, ITI Wagner
  • Inhalt: Diese Arbeit beschäftigt sich mit dem Finden zeitabhängiger energieoptimaler Routen. Es wird gezeigt, dass dieses Problem NP-schwer ist und auf dessen Komplexität eingegangen. Weiterhin werden drei Algorithmen vorgestellt, die energieoptimale Routen in zeitabhängigen Straßennetzwerken finden. Unter diesen befindet sich eine Heuristik, die nicht immer eine optimale Lösung liefert, dafür aber deutlich schneller ist als die beiden anderen Algorithmen. Die drei Algorithmen werden experimentell ausgewertet und es stellt sich heraus, dass nur die Heuristik schnell genug ist, um in der Praxis eingesetzt zu werden.

Optimierung von Straßenbeschriftungen einer Karte bezüglich zweier Maßstäbe

  • Date: Fri, 22 Apr 2016, 14:00
  • Location: SR 301
  • Speaker: Almut Demel, Abschlussarbeit, ITI Wagner
  • Inhalt: Landkarten helfen dabei, sich in unbekannten Umgebungen zurechtzufinden. Um einen Kartenausschnitt besser einer realen Umgebung zuordnen zu können werden die dargestellten Objekte mit Beschriftungen versehen. Interaktive Landkarten sind Landkarten, deren Maßstab veränderlich ist. Die Beschriftungen werden dabei je nach Maßstab angepasst, damit immer möglichst viele Straßen identifizierbar sind. Insbesondere in Navigationsgeräten in Fahrzeugen ist es dabei wichtig, einen fließenden Übergang zwischen den verschiedenen Beschriftungen zu finden, um möglichst wenig Ablenkung zu schaffen. Thema des Vortrags ist ein Algorithmus, der einen fließenden Übergang zwischen den Beschriftungen von Straßenkarten zweier Maßstäbe erzeugt. Dabei wird von einer festen Beschriftung in einem der beiden Maßstäbe ausgegangen, auf deren Grundlage eine Beschriftung für den zweiten Maßstab berechnet wird, die der ersten ähnelt und trotzdem viele Straßen identifizierbar macht. Mittels dynamischer Programmierung wird eine optimale Lösung für jede Straße einzeln berechnet. Durch eine Heuristik werden die gefundenen Beschriftungen zu einer Beschriftung des dargestellten Kartenausschnitts zusammengefügt.

Zeitabhängige energieoptimale Routen für Elektrofahrzeuge

  • Date: Tue, 12 Apr 2016, 14:00
  • Location: SR 301
  • Speaker: Oliver Thal, Bachelorarbeit, ITI Wagner
  • Inhalt: Diese Arbeit beschäftigt sich mit dem Finden zeitabhängiger energieoptimaler Routen. Es wird gezeigt, dass dieses Problem NP-schwer ist und auf dessen Komplexität eingegangen. Weiterhin werden drei Algorithmen vorgestellt, die energieoptimale Routen in zeitabhängigen Straßennetzwerken finden. Unter diesen befindet sich eine Heuristik, die nicht immer eine optimale Lösung liefert, dafür aber deutlich schneller ist als die beiden anderen Algorithmen. Die drei Algorithmen werden experimentell ausgewertet und es stellt sich heraus, dass nur die Heuristik schnell genug ist, um in der Praxis eingesetzt zu werden.

Experimentelle Untersuchung der Existenz planarer Greedy-Zeichnungen von Graphen

  • Date: Tue, 5 Apr 2016, 14:00
  • Location: SR 301
  • Speaker: Johannes Ernst, Bachelorarbeit