Research Seminar

Spring 2017

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

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

TBA

  • 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

Fall 2015

On drawing planar triangulations with bends

  • Date: Fri, 18 Mar 2016, 14:00
  • Location: SR 301
  • Speaker: Denis Knöpfle, Masterarbeit
  • Inhalt: According to the previously conducted user studies, increasing the number of bends decreases the understandability of a graph drawing. In this thesis we want to analyze whether in certain circumstances existing graph layouts can be improved by introducing bends. We have conducted a user study to compare straight-line graph drawings with their corresponding drawings that have bends and tested the user preference and performance on general tasks on both types of layouts. While in the experiment conducted in the past the bends have been assigned at random and bends on the same edge have different curvature, we assign the bends to the edges in an “intelligent” way and keep the polyline edges “smooth”, that is, without sharp corners and with the same curvature. Our experiment shows that “intelligently” placed bends do not have a significant negative impact on the readability, and that the aesthetic quality of the straight line and polyline drawings is comparable. Further, we take a closer look at several traditional metrics that measure the aesthetics of the drawings. Our experiments show that neither of the metrics captures the human feeling of aesthetics.

Optimization of Mobile Client-Server-Applications

  • Date: Thu, 3 Mar 2016, 14:00
  • Location: SR 301
  • Speaker: Thomas Breitbach, Technische Hochschule Mittelhessen
  • Inhalt: Nowadays, smartphones are full-time companions, facilitating the handling of important tasks and a steady flow of information. Unfortunately, the resources of the phones are most commonly unused in client-server-applications, with all the work being done server-side. To explain the objective and the complexity of the project in detail, bottlenecks and trade-offs will be identified first. Subsequently, a model showing subproblems like caching and prefetching will be developed. Based on the model, our recent work as well as the next steps of the project will be outlined.

TBA

  • Date: Tue, 16 Feb 2016, 14:00
  • Location: SR 301
  • Speaker: Jonas Fuchs, Masterarbeit

Well-shaped partitions of bipartite graphs through gradual convexity

  • Date: Mon, 15 Feb 2016, 14:00
  • Location: Raum 010
  • Speaker: Peter Eisenmann
  • Inhalt: This thesis is about the partitioning of graphs by using 'gradual convexity', a newly coined term, adhering to convex cuts, which describes a cut as convex to a certain degree. The Djokovic relation forms the basis for rating how gradually convex a cut is, for in a convex cut all cut-set edges are in this relation with one another. As there is no precise definition for gradual convexity (as of yet), multiple conceivable variants are derived. With the methods, resulting from these variants, simple cuts of bipartite graphs are rated. Based on their ratings, these simple cuts are combined to form new cuts. The goal is to determine a best rated cut.

Raum belegt

  • Date: Fri, 12 Feb 2016, 14:00
  • Location: SR 301
  • Speaker: IPD Snelting, (14:00-15:30)

Analyse und Optimierung des Raft Consensus Algorithmus in hochverteilten und performancekritischen Datenbanksystemen

  • Date: Tue, 2 Feb 2016, 14:00
  • Location: SR 301
  • Speaker: Nico Mürdter, Bachelorarbeitsvortrag (ITI Sanders)
  • Inhalt: Das Konsensproblem existiert seit Beginn der Verwendung von verteilten Systemen. Es beschreibt die Problematik der einheitlichen Zustandsänderung von Zustandsautomaten in einem Cluster. Alle Zustandsautomaten sollen jederzeit denselben Zustand aufweisen. Um dieses Problem zu lösen wurden Konsensalgorithmen formuliert, die die verteilte Haltung von Zustandsautomaten ermöglichen. Einer davon ist der von Diego Ongaro entwickelte Raft Consensus Algorithmus, dessen Ziel es ist, eine einfache und leicht verständliche Lösung zu liefern. Raft gehört zu den Leader-basierten Konsensalgorithmen. Das heißt, pro Cluster existiert immer ein eindeutiger Leader, welcher die Verwaltung und Steuerung des Clusters übernimmt. Somit verfügen solche Algorithmen auch über eine notwendige Leader Election. Es hat sich gezeigt, dass diese Leader Election in großen Clustern über 50 Knoten stark an Performanz verliert. Des Weiteren bietet sie keine aktive Möglichkeit, Knoten, die bei der Leader Election teilnehmen, unterschiedlich zu gewichten. Im Laufe dieser Arbeit konnte ein neuer Leader Election Algorithmus entwickelt werden, welcher einen Performancegewinn von bis zu Faktor 3 in großen Clustern, mit 100 Knoten generiert und eine aktive Gewichtung verschiedener Knoten ermöglicht. Es wurden Cluster von 5 bis 100 Knoten betrachtet und Timeouts von 150ms, 500ms und 1000ms getestet. Dabei ergab sich ein deutlicher Trend zu hohen Speedups in Clustern mit großen Timeouts und hohen Knotenzahlen. Durch diesen Speedup und die Möglichkeit, aktiv in die Leader Election einzugreifen, konnte die Auswahl eines Leaders innerhalb eines Raft Clusters deutlich verbessert werden.

Drawing Metro Maps on Concentric Circles

  • Date: Mon, 1 Feb 2016, 13:00
  • Location: SR 301
  • Speaker: Lukas Barth, Masterarbeitsvortrag (ITI Wagner)
  • Inhalt: We examine algorithms for the drawing of metro maps. The most important elements of a metro map are stations and lines connecting the stations. We restrict the elements used for representing lines to one of two classes: On the one hand, circular segments lying on circles with a common center S are allowed. On the other hand, line segments lying on lines passing through S are allowed. To make the metro maps as legible as possible, we try to create a drawing in which the lines bend as little as possible. To this end, we adapt the Topology-Shape-Metrics framework by Roberto Tamassia, the purpose of which originally is bend minimization in orthogonal drawings of graphs. To produce a compact drawing, we present a compaction approach based on Simulated Annealing. We practically evaluate the adapted framework for drawing metro maps with concentric circles and demonstrate its usability even for complex metro networks such as Berlin or London, at the same time also determining reasonable values for the parameters of our framework.

Algorithmische Grundlagen eines Routingdienstes fuer Luftfracht

  • Date: Fri, 29 Jan 2016, 14:00
  • Location: SR 301
  • Speaker: Julian Englert, Bachelorarbeitsvortrag (ITI Wagner)
  • Inhalt: Auf Basis des Connection Scan Algorithmus wurden die Grundlagen eines Routingdienstes geschaffen, der einige Randbedingungen beim Transport von Luftfracht berücksichtigt. Dazu zählen die physikalische Dimensionierung der Fracht (Abmaße, Gewicht, Gefahrgutklasse), die zur Verfügung stehenden Verkehrsträger (Flugzeuge, LKWs), die Arten von Flughäfen (Hubs, Stationen) und politische Vereinbarungen zum Frachttransport zwischen Staaten (Freiheiten der Luft)

How to partition a graph when you think like a vertex

  • Date: Wed, 20 Jan 2016, 11:30
  • Location: SR 236
  • Speaker: Jan Ebbing, Bachelorarbeitsvortrag (ITI Sanders)

Automatisierte Analyse komplexer Netzwerke

  • Date: Fri, 15 Jan 2016, 14:00
  • Location: SR 301
  • Speaker: Mark Erb, Studienarbeitsvortrag (ITI Meyerhenke)

Finding Attractive Routes for Bicycles and Pedelecs

  • Date: Tue, 12 Jan 2016, 14:00
  • Location: SR 301
  • Speaker: Philipp Glaser, Diplomarbeitsvortrag (ITI Wagner)
  • Inhalt: Radfahrer berücksichtigen bei ihrer Routenwahl meist mehrere Kriterien. Häufig ist die Gewichtung dieser Kriterien nicht fest, sondern hängt von den individuelle Vorlieben oder der momentanen Situation ab. Beispielsweise könnte ein Radfahrer kleine Verlängerungen der Reisezeit in Kauf nehmen, wenn die Alternative als sicherer empfunden wird. Auf der Grundlage des Multi-label-Setting-Algorithmus kombiniert mit A*, suchen wir zunächst die gesamte Pareto-Menge. Die Menge der Pareto-optimalen Routen wird allerdings schnell sehr groß, was nicht nur zu langen Laufzeiten führt, sondern auch bei der Routenplanung nicht weiterhilft. Deshalb betrachten wir verschiedene Heuristiken, um die Anzahl der gefundenen Routen zu verringern. Als Erstes untersuchen wir ?-Dominanz, bei der auch Routen dominiert werden, die mit der Pareto-Dominanz nicht vergleichbar sind. Die zweite untersuchte Heuristik basiert auf dem Ausschluss von Routen, die nur kurz von einer bereits gefundenen Route abweichen. Außerdem betrachten wir den Einfluss der Reihenfolge, in der die Routen gesucht werden, auf das Resultat und die Laufzeit.

Finding Near-Optimal Independent Sets at Scale

  • Date: Fri, 8 Jan 2016, 14:00
  • Location: SR 301
  • Speaker: Darren Strash, Probevortrag ALENEX
  • Inhalt: The independent set problem is NP-hard and particularly difficult to solve in large sparse graphs, which typically take exponential time to solve exactly using the best-known exact algorithms. In this work, we develop an advanced evolutionary algorithm, which incorporates kernelization techniques to compute large independent sets in huge sparse networks. A recent exact algorithm has shown that large networks can be solved exactly by employing a branch-and-reduce technique that recursively kernelizes the graph and performs branching. However, one major drawback of their algorithm is that, for huge graphs, branching still can take exponential time. To avoid this problem, we recursively choose vertices that are likely to be in a large independent set (using an evolutionary approach), then further kernelize the graph. We show that identifying and removing vertices likely to be in large independent sets opens up the reduction space--which not only speeds up the computation of large independent sets drastically, but also enables us to compute high-quality independent sets on much larger instances than previously reported in the literature. Authors: Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F. Werneck

k-way Hypergraph Partitioning via n-Level Recursive Bisection

  • Date: Fri, 18 Dec 2015, 15:00
  • Location: SR 301
  • Speaker: Sebastian Schlag, Probevortrag ALENEX
  • Inhalt: We develop a multilevel algorithm for hypergraph partition- ing that contracts the vertices one at a time. Using sev- eral caching and lazy-evaluation techniques during coarsen- ing and refinement, we reduce the running time by up to two-orders of magnitude compared to a naive n-level algo- rithm that would be adequate for ordinary graph partition- ing. The overall performance is even better than the widely used hMetis hypergraph partitioner that uses a classical mul- tilevel algorithm with few levels. Aided by a portfolio-based approach to initial partitioning and adaptive budgeting of imbalance within recursive bipartitioning, we achieve very high quality. We assembled a large benchmark set with 310 hypergraphs stemming from application areas such VLSI, SAT solving, social networks, and scientific computing. Ex- periments indicate that our algorithm is the method of choice for a wide range of hypergraph partitioning tasks. The algorithm presented in this work forms the basis of our hypergraph partitioning framework KaHyPar (Karlsruhe Hypergraph Partitioning).

Drawing Ordered Trees with Small Height (and Width)

  • Date: Tue, 8 Dec 2015, 13:15
  • Location: SR 301
  • Speaker: Johannes Batzill, Bachelorarbeitsvortrag (ITI Wagner)
  • Inhalt: A planar drawing of a graph in which every node is on one of $k$ horizontal layers is called a $k$-layer drawing of a graph. If every edge of the drawing is horizontal, vertical or between consecutive layers, we call the drawing an HVA-drawing. Restricting edges to be straight lines and trees to be ordered, we prove a tight upper bound on the maximal number of horizontal layers required for a layered drawing of an ordered tree, and provide a way to construct a drawing matching the upper bound. Furthermore, we provide a way to construct a layered HVA-drawing of an ordered tree that uses at most $1.5$ times the layers compared to the upper bound of unconstrained layered drawings. The advantage of a layered HVA-drawing is that we are also able to bound the number of required vertical layers, i.e., we are able to bound its area. The structure of our constructions base on the work of Suderman. Suderman presented tight lower and upper bounds on the height of different types of layered drawings of trees. However, he did not present an upper bound on the height of layered drawings of ordered trees.

Editing to (P5, C5)-free Graphs - a Model for Community Detection?

  • Date: Fri, 27 Nov 2015, 14:00
  • Location: SR 301
  • Speaker: Philipp Schoch, Bachelorarbeitsvortrag (ITI Wagner)
  • Inhalt: Bei der (eher informell definierten) Aufgabe der Erkennung von Communities versucht man in einem Graphen G = (V, E) eine bestimmte Partitionierung der Knotenmenge V in einzelne Teilmengen (sog. Communities) zu finden. Dabei sollen die Knoten innerhalb einer einzelnen Teilmenge (Community) stärker miteinander verbunden sein als die Knoten aus verschiedenen Teilmengen (Communities). Diese stärkere Verbindung innerhalb der Communities kann dabei auf eine gemeinsame Funktion oder eine gemeinsame Rolle hinweisen, die sich die Knoten aus derselben Community teilen. (P5, C5)-free editing bedeutet, dass man versucht, durch Hinzufügen und durch Löschen von Kanten einen Graphen G (P5, C5)-frei zu machen. (P5, C5)-frei bedeutet, dass der resultierende Graph G' keinen P5 und keinen C5 als knoteninduzierten Subgraph enthalten darf. Die Schwierigkeit besteht darin dies in möglichst wenigen Schritten zu tun. Das heißt, man soll die Anzahl an hinzugefügten und gelöschten Kanten minimieren. Das Thema dieser Bachelorarbeit ist die Frage, ob man mithilfe von (P5, C5)-free editing Communities in einem Graphen finden kann. Dies beinhaltet erstens die Frage wie aufwändig es ist das (P5, C5)-free editing Problem zu lösen. Und zweitens die Frage, ob die Zusammenhangskomponenten von dem editierten Graphen G' tatsächlich sinnvolle Communities für den ursprünglichen Graphen G definieren. Die Idee für die Bachelorarbeit stammt von einem Paper, das versucht mithilfe von (P4, C4)-free editing Communities zu finden. Die wichtigsten Resultate dieser Bachelorarbeit sind der Beweis der NP- Vollständigkeit des (P5, C5)-free editing Problems, die Adaption von Verfahren, um einige reale Graphen zu (P5, C5)-freien Graphen zu editieren sowie eine Analyse der auf diese Weise gefundenen Communities. Die Analyse zeigt, dass auf manchen Graphen wohldefinierte Communities gefunden werden, auf anderen dagegen mehrere Communities vereinigt werden.

Boosting Local Search for the Maximum Independent Set Problem

  • Date: Tue, 17 Nov 2015, 13:15
  • Location: SR 301
  • Speaker: Jakob Dahlum, Bachelorarbeitsvortrag (ITI Sanders)
  • Inhalt: An independent set of a graph $G = (V, E)$ with vertices $V$ and edges $E$ is a subset $S subseteq V$, such that the subgraph induced by $S$ does not contain any edges. The goal of the maximum independent set problem (MIS problem) is to find an independent set of maximum size. It is equivalent to the well-known vertex cover problem (VC problem) and maximum clique problem. This thesis consists of two main parts. In the first one we compare the currently best algorithms for finding near-optimal independent sets and vertex covers in large, sparse graphs. They are Iterated Local Search (ILS) by Andrade et al., a heuristic that uses local search for the MIS problem and NuMVC by Cai et al., a local search algorithm for the VC problem. As of now, there are no methods to solve these large instances exactly in any reasonable time. Therefore these heuristic algorithms are the best option. In the second part we analyze a series of techniques, some of which lead to a significant speed up of the ILS algorithm. This is done by removing specific vertices and structures within the graph, which have a low probability of being part of the MIS. These are vertices of high degree, vertices within dense subgraphs or the like. In addition, we analyze the behavior of the ILS algorithm when inserting the cut vertices back into the graph. We also perform exact reductions which reduce the graph’s complexity without destroying information about the MIS. We can revert them after running ILS on the reduced graph. We present the experimental results of the comparison of ILS and NuMVC, as well as the improvement of ILS by removing vertices and the like. The used instances are known graphs from literature like road maps, social networks, meshes and web graphs.

The Physical Travelling Salesperson Problem - An Approach With Turn Segments

  • Date: Fri, 13 Nov 2015, 14:30
  • Location: SR 301
  • Speaker: Lars Gottesbüren, Bachelorarbeitsvortrag (ITI Meyerhenke)

Probabilistic Neighborhood Queries

  • Date: Fri, 13 Nov 2015, 14:00
  • Location: SR 301
  • Speaker: Moritz von Looz

Abschlusspräsentationen

  • Date: Fri, 6 Nov 2015, 14:00
  • Location: SR 301
  • Speaker: PSE, (ITI Wagner)

Logistics and Optimization at Amazon

  • Date: Thu, 5 Nov 2015, 17:30
  • Location: HS -101
  • Speaker: Andrew V. Goldberg, Senior Principal Scientist, Amazon.com
  • Inhalt: We discuss optimization problems at Amazon Logistics. Amazon is the biggest online retailer, fulfilling millions of orders a day. This leads to many classical OR problems. In addition, many of these problems are NP-hard, big, stochastic, and interrelated. This makes Amazon Logistics an exciting environment for research in optimization, algorithms, and algorithm engineering.

Erweiterung partieller planerer orthogonaler Zeichnungen

  • Date: Fri, 30 Oct 2015, 14:30
  • Location: SR 301
  • Speaker: Stefan Rettenmayr, Bachelorarbeitsvortrag (ITI Wagner)
  • Inhalt: Thema dieser Bachelorarbeit ist die planare Erweiterbarkeit orthogonaler Zeichnungen. Das Problem der planaren Erweiterbarkeit behandelt die Frage, ob eine vorgegebene Zeichnung eines Subgraphen zu einer Zeichnung des gesamten Graphen erweitert werden kann, ohne Planarita?t zu verletzen. Wir geben einen kurzen U?berblick u?ber verwandte Arbeiten, insbesondere u?ber einen ku?rzlich entdeckten Linearzeitalgorith- mus fu?r topologische Zeichnungen. Anschließend betrachten wir das Problem der planaren Erweiterbarkeit fu?r zwei verschiedene Zeichenstile, orthogonale Zeichnungen und orthogonale Gitterzeichnungen. Fu?r orthogonale Gitterzeichnungen fu?hren wir zwei Reduktionen durch, um zu zeigen, dass das Problem NP-schwer ist, selbst unter der zusa?tzlichen Einschra?nkung, dass die Einbettung des gesamten Graphen fest ist. Fu?r orthogonale Zeichnungen hingegen ko?nnen wir das Problem auf den Fall topologischer Zeichnungen reduzieren und einen Linearzeitalgorithmus herleiten.

Energy-Optimal Routes for Electric Vehicles with Charging Stops

  • Date: Fri, 30 Oct 2015, 14:00
  • Location: SR 301
  • Speaker: Jonas Sauer, Bachelorarbeitsvortrag (ITI Wagner)
  • Inhalt: Die Bedeutung von Elektrofahrzeugen hat in den letzten Jahren stetig zugenommen. Dank steigender Batteriekapazitäten und zunehmender Verbreitung von Ladestationen für Elektrofahrzeuge werden Langstreckenrouten mit Ladestopps allmählich praktikabler. Während Routenplanungsprobleme für Elektrofahrzeuge bereits ausführlich untersucht wurden, hat sich nur wenig Forschung mit der Berücksichtigung von Ladestationen beschäftigt. In dieser Arbeit erweitern wir frühere Arbeiten zu diesem Thema und entwickeln zwei Algorithmen, die Energie-optimale Routen finden und dabei Ladestopps erlauben. Unser erster Algorithmus basiert auf einer multikriteriellen Kürzeste-Wege-Suche, die Pareto-Mengen verwendet. Obwohl multikriterielle Kürzeste-Wege-Algorithmen im Allgemeinen eine exponentielle Worst-Case-Komplexität haben, führen wir eine Klasse von Graphen ein, für die wir eine polynomielle Laufzeit unseres Algorithmus zeigen. Der zweite Algorithmus verwendet einen vorberechneten Graph, der die kürzesten Wege zwischen alle Ladestationen enthält, um die Anfragen zu beschleunigen. Wir werten unsere Algorithmen für echte Straßennetzwerkdaten aus und beobachten für beide Algorithmen Anfragezeiten im Sekundenbereich auf dem Straßennetzwerk Deutschlands.

Annotation von Texten unter Berücksichtigung von Textzwischenräumen

  • Date: Fri, 9 Oct 2015, 14:30
  • Location: SR 301
  • Speaker: Amrei Loose, Bachelorarbeitsvortrag (ITI Wagner)
  • Inhalt: Für die Arbeit mit Textdokumenten ist es mitunter nützlich wenn das Anfügen von Kommentaren möglich ist. Viele Textverarbeitungsprogramme ermöglichen es bereits Stellen im Text zu markieren und etwas anzufügen. Häufig werden diese Implementierungen aber bei einer grösseren Anzahl Kommentaren schnell unübersichtlich. Diese Arbeit beschäftigt sich mit einer kreuzungsfreien Lösung für die Randbeschriftung in Texten, wobei die gefundene Lösung keine Überschneidungen mit dem Text aufweisen soll. Dafür werden zwei verschiedene Ansätze betrachtet: Der erste Ansatz verwendet opo-Leader für die Beschriftung und berechnet mithilfe eines Clusterings der Label eine Beschriftung. Dieser Ansatz besitzt eine Laufzeit in O(n log n). Der zweite Ansatz basiert auf einem Flussnetzwerk, in welchem mithilfe eines maximalen Flusses minimalen Gewichts eine optimale Lösung berechnet werden soll.

New Results on Trajectory Grouping under Geodesic Distance

  • Date: Fri, 9 Oct 2015, 14:00
  • Location: SR 301
  • Speaker: Jérôme Urhausen, Bachelorarbeitsvortrag (ITI Wagner)
  • Inhalt: Technology nowadays allows us to easily track the position of humans and animals alike. When repeated multiple times, one obtains trajectories describing the movement of the observed entities. This data provides information about which entities assemble and form groups and how these groups evolve over time. We extend the results of Kostitsyna et al. who studied the grouping of entities in scenarios with polygonal obstacles. We prove that in some cases fast algorithms can neither compute an explicit representation of the evolution of the groups, nor use all epsilon-events. These epsilon-events occur when the geodesic distance between two entities is epsilon, which is the threshold distance determining if two entities are in the same group. Moreover, we present a new algorithm for trajectory grouping with obstacles. The algorithm is signi?cantly faster than the previously known one, if the amount of observed entities is signi?cantly bigger than the total complexity of the obstacles. In addition we provide evidence that if obstacles are big compared to epsilon, then the worst-case size of the output does not depend on the complexity of the obstacles. Finally we present an efficient algorithm for said big obstacles.

Spring 2015

Correspondences between Partitions and their Computation

  • Date: Wed, 23 Sep 2015, 13:00
  • Location: SR 301
  • Speaker: Roland Glantz
  • Inhalt: Partitions/clusterings are instrumental in tasks such as classification, pattern recognition and network analysis. In the past, an abundance of similarity measures for pairs (C, C') of partitions (clusterings) of the same ground set have been proposed. Such a measure for the overall similarity of C and C', however, does not provide specifics on what the similarities/correspondences between C and C' consist in, e.g., when the union of two clusters in C is similar to a cluster in C'. We think of a correspondence between C and C' as a pair (B, B'), where B [B'] is a subset (block) of C [C'], and the symmetric difference between the union of clusters in B and the union of clusters in B' has low cardinality. Weights of elements in the ground set can be taken into account through replacing ``cardinality'' by ``total weight''. We show that such an objective function is essentially one for blocks of C only, since (i) the objective function can be written without B' and (ii) finding the optimal partner B' for any B is straight-forward. The objective function's value for B is a measure for the fragmentation of B w.r.t. C'. Analogous to graphs, a C_s-C_t cut of C is a pair (B, C - B) such that B contains C_s but not C_t. We show how one can compute a Gomory-Hu tree T of optimal C_s-C_t cuts (optimal w.r.t the fragmentation of B) using a branch-and-bound approach. The tree T defines a hierarchical decomposition of C and also gives rise to the best correspondences between C and C'.

On Minimizing Crossings in Storyline Visualizations

  • Date: Fri, 18 Sep 2015, 14:00
  • Location: SR 301
  • Speaker: Darren Strash, Practice talk for GD 2015
  • Inhalt: In a storyline visualization, we visualize a collection of interacting characters (e.g., in a movie, play, etc.) by $x$-monotone curves that converge for each interaction, and diverge otherwise. Given a storyline with $n$ characters, we show tight lower and upper bounds on the number of crossings required in any storyline visualization for a restricted case. In particular, we show that if (1) each meeting consists of exactly two characters and (2) the meetings can be modeled as a tree, then we can always find a storyline visualization with $O(nlog n)$ crossings. Furthermore, we show that there exist storylines in this restricted case that require $Omega(nlog n)$ crossings. Lastly, we show that, in the general case, minimizing the number of crossings in a storyline visualization is fixed-parameter tractable, when parameterized on the number of characters $k$. Our algorithm runs in time $O(k!^2klog k + k!^2m)$, where $m$ is the number of meetings.

Parallel Graph Algorithms on the Xeon Phi Coprocessor

  • Date: Mon, 7 Sep 2015, 14:00
  • Location: Raum 010
  • Speaker: Dennis Felsing, Masterarbeitsvortrag (ITI Meyerhenke)
  • Inhalt: In this thesis two graph algorithms, one for graph generation, the other for graph visualization are studied examplarily. We detail the work of adapting and porting the algorithms to the Intel Xeon Phi coprocessor architecture. Problems in porting real software projects and used libraries are encountered and solved. Memory allocations turned out to be a major problem for the graph generation algorithm. The limited memory of the Xeon Phi forced us to offload chunks of the data from the host system to the Xeon Phi, which impeded performance, eliminating any significant speedup. The data sets for the graph visualization algorithm fir into the Xeon Phi's memory easily, which simplified the porting process significantly. We achieve a speedup for sparse graphs over the host system containing two 8-core Intel Xeon (Sandy Bridge) processors.

Efficient Enumeration of All Reasonable Journeys in Public Transport Networks

  • Date: Thu, 3 Sep 2015, 15:00
  • Location: SR 301
  • Speaker: David Weiß, Masterarbeitsvortrag
  • Inhalt: Recent research on route planning in public transport networks mostly focused on customer perspective of answering individual queries for specific journeys in realtime. We shift this focus towards the viewpoint of traffic planners, who need to enumerate all reasonable journeys throughout the network over a given timespan at once, to e.g. compute demand data down to specific lines and vehicles. While realtime is not an issue, faster algorithms that incorporate realistic footpath models, are required to make all-to-all journey enumerations feasible for large networks. Also, the extraction of concrete journey representations becomes a substantial and time consuming part. We present an algorithm for searching and enumerating journeys which are optimal in the Pareto sense in regard to travel time and number of transfers between all pairs of destinations. The algorithm is capable of handling realistic transfer models as well as reasonable footpath networks. For our real world test data incorporating 1,156 distinct destinations, we manage to enumerate 388,471,381 optimal journeys, averaging 291 journeys per destination pair, in less than 33 minutes or 5 microseconds per journey. Exploiting the embarrassingly parallelizable structure of our algorithm, concurrent enumeration using 8 cpu cores with a speed up of 5.6 brings down computation time to about 5.8 minutes.

Parallel Lightweight Wavelet-Tree, Suffix-Array and FM-Index Construction

  • Date: Thu, 27 Aug 2015, 15:00
  • Location: SR 236
  • Speaker: Julian Labeit, Bachelorarbeitsvortrag (ITI Sanders)
  • Inhalt: We present parallel lightweight algorithms to construct rank and select structures, wavelet trees and suffix arrays in a shared memory setting. In experiments the presented wavelet tree algorithms achieve a speedup of 2-4x over existing parallel algorithms while reducing the asymptotic memory requirement. The suffix array construction algorithm presented is the first parallel algorithm using the induced copying approach. It only uses a small amount of extra space while staying competitive with existing parallel algorithms. Finally, we show how our algorithms can be used to build compressed full-text indexes, such as the FM-index, in parallel.

Engineering Initial Partitioning Algorithms for direct k-way Hypergraph Partitioning

  • Date: Wed, 26 Aug 2015, 09:00
  • Location: SR 236
  • Speaker: Tobias Heuer, Bachelorarbeitsvortrag (ITI Sanders)

Pareto-Optimization of Travel Time and the Number of Turns in Road Networks

  • Date: Tue, 18 Aug 2015, 14:00
  • Location: SR 301
  • Speaker: Benjamin Davis, Bachelorarbeitsvortrag

Structure-Preserving Sparsification of Social Networks

  • Date: Tue, 18 Aug 2015, 13:00
  • Location: SR 301
  • Speaker: Gerd Lindner, ASONAM Probevortrag
  • Inhalt: Sparsification reduces the size of networks while preserving structural and statistical properties of interest. Various sparsifying algorithms have been proposed in different contexts. We contribute the first systematic conceptual and experimental comparison of edge sparsification methods on a diverse set of network properties. It is shown that they can be understood as methods for rating edges by importance and then filtering globally by these scores. In addition, we propose a new sparsification method (Local Degree) which preserves edges leading to local hub nodes. All methods are evaluated on a set of 100 Facebook social networks with respect to network properties including diameter, connected components, community structure, and multiple node centrality measures. Experiments with our implementations of the sparsification methods (using the open-source network analysis tool suite NetworKit) show that many network properties can be preserved down to about 20% of the original set of edges. Furthermore, the experimental results allow us to differentiate the behavior of different methods and show which method is suitable with respect to which property. Our Local Degree method is fast enough for large-scale networks and performs well across a wider range of properties than previously proposed methods.

Optimal Shuffle Code with Permutation Instructions (Probevortrag für WADS)

  • Date: Tue, 28 Jul 2015, 14:00
  • Location: SR 301
  • Speaker: Manuel Mohr, IPD Snelting
  • Inhalt: During compilation of a program, register allocation is the task of mapping program variables to machine registers. During register allocation, the compiler may introduce emph{shuffle code}, consisting of copy and swap operations, that transfers data between the registers. Three common sources of shuffle code are conflicting register mappings at joins in the control flow of the program, e.g, due to if-statements or loops; the calling convention for procedures, which often dictates that input arguments or results must be placed in certain registers; and machine instructions that only allow a subset of registers to occur as operands. Recently, Mohr et al. [2013] proposed to speed up shuffle code with special hardware instructions that arbitrarily permute the contents of up to five registers and gave a heuristic for computing such shuffle codes. In this paper, we give an efficient algorithm for generating optimal shuffle code in the setting of Mohr et al. An interesting special case occurs when no register has to be transferred to more than one destination, i.e., it suffices to permute the contents of the registers. This case is equivalent to factoring a permutation into a minimal product of permutations, each of which permutes up to five elements.

Fast Computation of Isochrones in Road Networks

  • Date: Fri, 24 Jul 2015, 15:00
  • Location: SR 301
  • Speaker: Valentin Buchhold, Masterarbeitsvortrag (ITI Wagner)
  • Inhalt: Wir untersuchen das Problem, in einem Straßennetz Isochronen effizient zu berechnen. Intuitiv ist eine Isochrone die Region, die innerhalb einer gewissen Zeit von einem fixen Startpunkt erreicht werden kann. Praktische Anwendungen sind Erreichbarkeitsanalysen in der Städteplanung, Geomarketing und die Anzeige der verbleibenden Reichweite eines Fahrzeugs. Wir stellen verschiedene formale Definitionen aus der Literatur zusammen und präsentieren mehrere Algorithmen zur Berechnung von Isochronen. Neben der Erweiterung von bekannten Beschleunigungstechniken schlagen wir eine neue Familie von Algorithmen zur Berechnung von Isochronen vor, die auf Graphenseparatoren und Contraction-Hierarchies aufbaut. Dagegen basieren bestehende Ansätze auf Multilevel-Dijkstra-Suchen. Wir schließen mit einer experimentellen Evaluation unserer Algorithmen.

Route planning for electric vehicles and preliminary studies on traffic pattern classification

  • Date: Fri, 10 Jul 2015, 14:15
  • Location: SR 301
  • Speaker: Shao-Chieh, Intern student from National Tsing Hua University, Taiwan

Online energy scheduling problem

  • Date: Fri, 10 Jul 2015, 14:00
  • Location: SR 301
  • Speaker: I-Hsuan, Intern student from National Tsing Hua University, Taiwan

Algorithms for Contraction Hierarchies on Public Transit Networks

  • Date: Tue, 7 Jul 2015, 13:15
  • Location: SR 301
  • Speaker: Alexander Wirth, Diplomarbeitsvortrag (ITI Wagner)
  • Inhalt: Modern applications for route planning in public transit networks require algorithms that can answer earliest arrival queries within milliseconds. This thesis revits Contraction Hierarchies as a preprocessing technique for time-dependent transit networks of various sizes in order to achieve faster query times. We evaluate existing algorithms and propose alternative approaches for earliest arrival queries and profile queries that work on both the contracted and uncontracted networks. We also provide an alternative algorithm for finding witnesses during the construction of the hierarchy and show how it can be extended to allow a combination of time-dependent and time-independent edges. Finally, we evaluate the algorithms on real public transit networks of various sizes.

Separators in Planar Graphs and Road Networks

  • Date: Fri, 26 Jun 2015, 15:00
  • Location: SR 301
  • Speaker: Christian Sommer, PhD, Apple
  • Inhalt: Graph Partitioning is the well-studied problem of cutting a graph into disjoint regions of approximately equal size while minimizing the number of edges between regions. Graph partitions are used as essential building blocks in various efficient algorithms. One way of obtaining a partition is by cutting the graph into two pieces and then recursing on each subgraph. The recursion ends when the resulting subgraphs are sufficiently small. This way of partitioning is known as recursive bisection. Recursive bisection works well for those graphs that have small balanced separators. We review theoretical and experimental results on separators in planar graphs and road networks. For planar graphs (and, more generally, minor-free graphs), separator theorems have been known for decades. More recently, even smaller separators have been found for road networks. Joint work with Philip Klein and Shay Mozes (planar separators) and Aaron Schild (road network separators)

Graph partitioning for independent sets

  • Date: Fri, 26 Jun 2015, 14:00
  • Location: SR 301
  • Speaker: Sebastian Lamm, SEA Probevortrag

Proportional Contact Representation of Planar Graphs

  • Date: Wed, 24 Jun 2015, 14:00
  • Location: Mittlerer Hörsaal, Gebäude 10.91 - Maschinenbau
  • Speaker: Prof. Stephen Kobourov, University of Arizona, im Rahmen der
  • Inhalt: In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. We show how to use Schnyder realizers and canonical orders for planar graphs to obtain different types of contact representations. Specifically, we describe an algorithm that guarantees 10-sided rectilinear polygons and runs in linear time. We also describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time. However, to compute the exact representation from the area-universal layout required numerical iteration, or can be approximated with a hill-climbing heuristic.

From Graphs to Maps

  • Date: Tue, 23 Jun 2015, 09:45
  • Location: SR 301
  • Speaker: Prof. Stephen Kobourov, University of Arizona, Im Rahmen der VL Algorithmische Kartografie
  • Inhalt: Relational data sets are often visualized with graphs: objects become the graph vertices and relations become the graph edges. Graph drawing algorithms aim to present such data in an effective and aesthetically appealing way. We describe map representations, which provide a way to visualize relational data with the help of conceptual maps as a data representation metaphor. While graphs often require considerable effort to comprehend, a map representation is more intuitive, as most people are familiar with maps and ways to interact with them via zooming and panning. Map-based visualization allows us to explicitly group clusters of related vertices as "countries" and to present additional information with contour and heatmap overlays. We consider map representations of the DBLP bibliography server. Words and phrases from paper titles are the cities in the map, and countries are created based on word and phrase similarity, calculated using co-occurence. With the help of heatmaps, we can visualize the profile of a particular conference or journal over a base map of all computer science. Similarly, we can create heatmap profiles for individual researchers or research groups such as a department. Alternatively, a specific journal or conference can be used to generate the base map and then a series of heatmap overlays can show the evolution of research topics in the field over the years. As before, individual researchers or research groups can be visualized using heatmap overlays but this time over the journal or conference base map. Finally, visual abstracts can be generated from research papers, providing a snapshot view of the topics in the paper. See http://mocs.cs.arizona.edu for more details.

Tree compression with top trees revisited

  • Date: Fri, 19 Jun 2015, 15:00
  • Location: SR 301
  • Speaker: Lorenz Hübschle-Schneider, SEA Probevortrag
  • Inhalt: We revisit tree compression with top trees (Bille et al, ICALP'13) and present several improvements to the compressor and its analysis. By significantly reducing the amount of information stored and guiding the compression step using a RePair-inspired heuristic, we obtain a fast compressor achieving good compression ratios, addressing an open problem posed by Bille et al. We show how, with relatively small overhead, the compressed file can be converted into an in-memory representation that supports basic navigation operations in worst-case logarithmic time without decompression. We also show a much improved worst-case bound on the size of the output of top-tree compression (answering an open question posed in a talk on this algorithm by Weimann in 2012).

A bulk-parallel priority queue in external memory with STXXL

  • Date: Fri, 19 Jun 2015, 14:30
  • Location: SR 301
  • Speaker: Thomas Keh, SEA Probevortrag
  • Inhalt: We present the design and implementation of a bulk-parallel priority queue which takes advantage of both shared-memory parallelism and high external memory transfer speeds to parallel disks. To achieve higher performance by decoupling item insertions and extractions, we offer a new interface using "bulk" sequences. We discuss how to parallelize insertions using multiple heaps, and how to calculate a dynamic prediction sequence to prefetch blocks and apply parallel multiway merge for extraction.

How to Draw a Planarization

  • Date: Fri, 19 Jun 2015, 14:00
  • Location: SR 301
  • Speaker: Marcel Radermacher, Masterarbeitsvortrag (ITI Wagner)
  • Inhalt: In this thesis we study the problem of computing a straight-line representation of a planarization with a fixed combinatorial structure. By the results of Mnëv and Shor this problem is as hard as the Existential Theory of the Reals (ER-Complete). We present a heuristic called Geometric Planarization Drawing to compute a straight-line representation of a planarization. We take an iterative approach inspired by a force-directed method utilizing geometric operations to place a vertex to a locally optimal position. The core of our algorithm is the planarity region, in which we can move a vertex without changing the embedding. We take a statistical approach to evaluate the final drawings of different configurations of our Geometric Planarization Drawing approach. The evaluation shows that we improve the initial drawing, and find better results than our implementation of a force-directed method based on PrEd. Depending on the number of crossings per edge, a relaxation of the constraints improves the final drawing. To the best of our knowledge, the Geometric Planarization Drawing approach is the first heuristic to tackle the problem of straight-line representations of a planarization. In practice, our algorithms finds close to optimal solutions for drawings with at most 3 crossings per edge.

Cache-Efficient Aggregation: Hashing Is Sorting

  • Date: Wed, 17 Jun 2015, 11:30
  • Location: SR 236
  • Speaker: Ingo Müller
  • Inhalt: For decades researchers have studied the duality of hashing and sorting for the implementation of the relational operators, especially for efficient aggregation. Depending on the underlying hardware and software architecture, the specifically implemented algorithms, and the data sets used in the experiments, different authors came to different conclusions about which is the better approach. In this paper we argue that in terms of cache efficiency, the two paradigms are actually the same. We support our claim by showing that the complexity of hashing is the same as the complexity of sorting in the external memory model. Furthermore we make the similarity of the two approaches obvious by designing an algorithmic framework that allows to switch seamlessly between hashing and sorting during execution. The fact that we mix hashing and sorting routines in the same algorithmic framework allows us to leverage the advantages of both approaches and makes their similarity obvious. On a more practical note, we also show how to achieve very low constant factors by tuning both the hashing and the sorting routines to modern hardware. Since we observe a complementary dependency of the constant factors of the two routines to the locality of the input, we exploit our framework to switch to the faster routine where appropriate. The result is a novel relational aggregation algorithm that is cache-efficient---independently and without prior knowledge of input skew and output cardinality---, highly parallelizable on modern multi-core systems, and operating at a speed close to the memory bandwidth, thus outperforming the state-of-the-art by up to 3.7x.

Informatikkolloquium: Visibility and Transformation of Paths in Simple Polygons

  • Date: Mon, 15 Jun 2015, 17:30
  • Location: Hörsaal -101
  • Speaker: Professor Subir Ghosh, IIT Mumbai
  • Inhalt: Let s be a source point and t be a destination point inside an n-vertex simple polygon P. Let SP(s,t) denote the Euclidean shortest path, the path of the shortest length, from s to t inside P. Similarly, let MLP(s,t) denote a minimum link path, a path of the minimum number of turns, from s to t. We know that these two paths are simple and piece-wise convex. A path from a light source s to t inside P is called a diffuse reflection path (denoted as drp(s,t)) if the turning points of the path lie in the interiors of the boundary edges of P. A drp(s,t) is said to be optimal if it has the minimum number of turning points amongst all drp(s,t). An optimal drp(s,t) may not be simple. In this talk, we first show how SP(s,t) can be transformed to a MLP(s,t) and then we show that MLP(s,t) can also be transformed to a drp(s,t).

Engineering Fully-Compressed Suffix Trees

  • Date: Fri, 12 Jun 2015, 14:00
  • Location: SR 301
  • Speaker: Christian Ocker, Masterarbeitsvortrag (ITI Sanders)
  • Inhalt: The suffix tree is a classical data structure that provides optimal solutions to countless string processing problems. For a text of length n, a pointer- based representation of a suffix tree requires ?(n log n) bits, whereas compact representations use O(n) bits on top of the size of the compressed text. The fully-compressed suffix tree (FCST) provides the same functionality using o(n) bits on top of the size of the compressed text, whereas queries are slowed down by a logarithmic factor compared to compact representations. Our contribution is a generic implementation of the FCST and of a recent proposal by Navarro and Russo that uses a different sampling to achieve a better query time complexity. We propose a variant of the FCST that improves pattern matching both in theory and in practice using a blind search approach. We provide an extensive empirical evaluation and comparison of the implemented data structures and show that out implementation outperforms the previous prototype in both space consumption and query/construction time.

Practical Massively Parallel Sorting

  • Date: Tue, 9 Jun 2015, 13:10
  • Location: SR 301
  • Speaker: Michael Axtmann, Probevortrag SPAA 2015

Informatikkolloquium: Analyzing the Language of Food on Social Media

  • Date: Mon, 8 Jun 2015, 17:30
  • Location: Hörsaal -101
  • Speaker: Prof. Stephen G. Kobourov, University of Arizona
  • Inhalt: We investigate the predictive power behind the language of food on social media. We collect a corpus of over three million food-related posts from Twitter and demonstrate that many latent population characteristics can be directly predicted from this data: overweight rate, diabetes rate, political leaning, and home geographical location of authors. For all tasks, our language-based models significantly outperform the majority- class baselines. Performance is further improved with more complex natural language processing, such as topic modeling. We analyze which textual features have most predictive power for these datasets, providing insight into the connections between the language of food, geographic locale, and community characteristics. Lastly, we design and implement an online system for real-time query and visualization of the dataset. Visualization tools, such as geo-referenced heatmaps, semantics-preserving wordclouds and temporal histograms, allow us to discover more complex, global patterns mirrored in the language of food.
  • Date: Tue, 2 Jun 2015, 13:00
  • Location: Raum 010
  • Speaker: Kolja Esders, Bachelorarbeitsvortrag (ITI Meyerhenke)
  • Inhalt: Link prediction methods try to predict the likelihood of a future connection between two nodes in a given network. This can be used in biological networks to infer protein-protein interactions or to suggest possible friends to a user in an online social network. Due to the enormous amounts of data that is collected today, there is a need for scalable approaches to this problem. In this thesis, we make use of machine learning and evaluate nine unsu- pervised as well as three supervised methods on six networks with the Receiver Operating Characteristic (ROC) and Precision-Recall (PR) metrics. To investigate the implications of different experimental setups, the testing and training set are varied in size and den- sity. We also introduce a new local index called Neighborhood Distance. The experiments show that supervised methods consistently outperform unsupervised methods by up to 7.2% with respect to the ROC metric. The overall prediction quality is also highly depen- dent on the properties and structure of the analyzed network. In an effort to parallelize predictors, we achieve a speedup of more than ten. The findings suggest that generating custom predictoars for networks based on their properties deserves further research.

Partitioning and Repartitioning Using Size-Constrained Label Propagation and NetworKit

  • Date: Thu, 21 May 2015, 14:30
  • Location: SR 131
  • Speaker: Patrick Bisenius, Bachelorarbeitsvortrag (ITI Meyerhenke)
  • Inhalt: Multilevel graph partitioning schemes have proven very effective in practice. As part of this thesis, we implement a multilevel graph partitioner based on Size-constrained Label Propagation in NetworKit which achieves comparable solution quality to the established partitioners KaHIP and ParMETIS for partitioning and repartitioning. We also evaluate several strategies to improve existing partitioners such as better tie-breaking strategies in the Label Propagation Algorithm and the application of Edge Ratings for Label Propagation. We achieve considerable runtime improvements compared to KaHIP on certain graphs by speeding up certain phases of the multilevel partitioner. Finally, we implement and evaluate a greedy algortihm to optimize the maximum communication volume of a k-partition.

Soon on SIGMOD: "SimpleMinds" in the SIGMOD Programming Contest

  • Date: Thu, 21 May 2015, 09:45
  • Location: SR -118
  • Speaker: Ingo Müller
  • Inhalt: Authors: Ismail Oukid (TU Dresden/SAP SE), Ingo Müller (KIT/SAP SE), Iraklis Psaroudakis (EPFL/SAP SE) Contest website: http://db.in.tum.de/sigmod15contest/ Duration: 30 minutes presentation + 15 minutes questions and feedback

Iterative Local Community Detection Combining Graph Structure and Attribute Similarity

  • Date: Tue, 19 May 2015, 13:00
  • Location: SR 301
  • Speaker: Jonas Krautter, Bachelorarbeitsvortrag (IPD Böhm, ITI Wagner)
  • Inhalt: Graph clustering has received a lot of attention by scientists and many algorithms have been developed to approximate solutions to variants of the problem, which is usually NP-hard. Lately methods have been proposed to combine attribute information and graph topology into the clustering process. However, none of the available combining algorithms offers a local approach, able to detect a community around a given seed node or a set of seed nodes. Therefore, we present an iterative solution in this thesis: Learning attributes in a local environment, adding edges to represent attribute similarity and using a known local structural algorithm, to provide a method for local community detection that respects both graph structure and attribute data. Evaluation results of the method on synthetic data and real world data from the Facebook friendship network and the Amazon co-purchase network prove the usefulness of the method to improve the detection of communities and identify communities in overlapping structures.

Label Propagation for Hypergraph Partitioning

  • Date: Tue, 12 May 2015, 13:00
  • Location: SR 301
  • Speaker: Vitali Henne, Masterarbeitsvortrag (ITI Sanders)

Experimental Evaluation of Distributed Node Coloring Algorithms in the SINR Model

  • Date: Tue, 5 May 2015, 13:00
  • Location: SR 301
  • Speaker: Markus Schlegel, Bachelorarbeitsvortrag (ITI Wagner)
  • Inhalt: One approach to minimizing interference in ad hoc or sensor networks is to limit the number of concurrently transmitting nodes in every neighborhood by using a specific periodic TDMA schedule. Such a TDMA schedule ensures that nodes, which are neighbors in the communication graph, are transmitting in different time slots. Establishing such a schedule is closely related to the node coloring problem. In a properly colored graph, two neighboring nodes are never assigned the same color. In consequence, if we map each color to a slot in the periodic TDMA schedule, neighboring nodes are never allowed to transmit in the same time slot. In this thesis, we experimentally evaluate the runtime performance of three distributed node coloring algorithms in the Signal to Interference and Noise Ratio model (SINR) with the help of the network simulator framework sinalgo. Additionally we look at some practical improvements and evaluate their impact on the execution time.

An in depth look at LU-decomposition on modern multi-socket hardware

  • Date: Wed, 29 Apr 2015, 13:00
  • Location: SR 301
  • Speaker: Tobias Maier, Masterarbeitsvortrag (ITI Sanders)
  • Inhalt: Modern hardware makes new demands on algorithms. To properly utilize multi-socket architectures with non-trivial cache hierarchies, algorithms have to be designed with the hardware’s strengths, and weaknesses in mind. If properly addressed, modern hardware offers new, and interesting optimization possibilities. In this thesis we present a new scheduling approach, using the example of an LU-decomposition. Our scheduler considers data reuse opportunities between different subtasks, and schedules these subtasks in a way that lets them share common inputs through the L3 cache. The LU-decomposition of matrices is one of the most important numerical algorithms. It is used for matrix inversion, to compute the determinant of a matrix, and to solve systems of linear equations. The algorithm for LU-decomposition is also representative for many other numerical computations. This is the reason, why it is part of the famous LINPACK benchmark, that is used to rank the most powerful supercomputers in the TOP500 list. It is important, to improve the performance of the LU-decomposition, without decreasing its numerical accuracy. Therefore, we use the same numerical algorithm for the LU-decomposition as PLASMA (Parallel Linear Algebra for Scalable Multi-core Architectures), which is a current state of the art implementation. By adapting the scheduling scheme, to take better advantage of data sharing, we achieve performance increases between 15%, and 29%.

Connecting Points with Low-Complexity Polynomial Curves in a Polygon

  • Date: Tue, 21 Apr 2015, 13:00
  • Location: SR 301
  • Speaker: Fabian Klute, Masterarbeitsvortrag (ITI Wagner)
  • Inhalt: Adding an edge to an already existing graph drawing can be done in a lot of ways. In my thesis we explored the possibility to draw the edge using a polynomial curve. Generalizing the k-link-path problem to curves the problem can be stated as finding a curve that connects two points, while respecting a given bounding polygon. For degree two curves we present a direct algorithmic solution. For any curve with higher degree the problem is more difficult to solve. Sampling the control points is the logical next step. With a naive approach one needs an exponential amount of sample points, but using epsilon-nets, we proved that a small set of points is sufficient to find a set of control points.

Consumption and Travel Time Profiles in Electric Vehicle Routing

  • Date: Fri, 17 Apr 2015, 14:00
  • Location: SR 301
  • Speaker: Simeon Andreev, Masterarbeitsvortrag (ITI Wagner)
  • Inhalt: Ein wichtiger Aspekt der Routenplanung für elektrische Autos ist der Trade-off zwischen Energieverbrauch und Reisezeit. Um diesen Trade-off möglichst allgemein zu berechnen, wurden in bisherigen Verfahren variable Fahrgeschwindigkeiten auf Straßensegmenten erlaubt: Pro Straßensegment ist dabei eine feste Anzahl an Geschwindigkeiten möglich. In meiner Masterarbeit wird dieser Ansatz um Kostenfunktionen erweitert, so dass der Geschwindigkeitsverlauf nicht mehr diskret ist. Dadurch liefert eine Profilsuche sowohl schnellere Anfragezeiten als auch ein kompakteres Ergebnis. Im Vortrag werde ich die dazu benötigten Profiloperationen, den Profilalgorithmus und eine Adaption der zeitabhängigen Contraction Hierarchies vorstellen. Am Ende des Vortrags steht die experimentelle Evaluation der vorgeschlagenen Algorithmen.