Wintersemester 2019

Edge Guarding Plane Graphs

  • Datum: Fr, 25 Okt 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Paul Jungeblut, ITI Wagner; Master's Thesis
  • Inhalt: Let G=(V,E) be a plane graph. We say that a face f is guarded by an edge vw if at least one of {v,w} is on the boundary of f. This talk presents the results of my master thesis giving bounds on the minimum number of edges needed to guard all faces of any n-vertex plane graph in some specific graph classes. After a general overview of previous and new results we will consider stacked triangulations in more detail: For the lower bound we construct particularly hard instances, for the upper bound we see how to locally reduce the size of a stacked triangulation to use induction on the number of vertices.

Improving Distributed External Sorting for Big Data in Thrill

  • Datum: Fr, 11 Okt 2019, 14:00
  • Ort: Raum 211
  • Vortragende(r): Jonas Dann, ITI Sanders; Master Thesis
  • Inhalt: Big data analytics and scientific computing require processing ever growing amounts of data. Competition between companies and between academics applies pressure to analyze data ever faster. In recent years, big data processing frameworks like Apache Spark, Apache Flink and Thrill came into popularity to aid this development. Such frameworks simplify the algorithm development significantly, by hiding most of the complexities of working with distributed computer clusters and disks. This talk focuses on Thrill. One of the most important nontrivial algorithmic primitive in these frameworks is sorting. Sorting accounts for a significant percentage of computer use overall. This talk will present the state of the art distributed external sorting algorithm Canonical Merge Sort. Canonical Merge Sort however shows weaknesses when sorting streams of data, since it only uses local knowledge about the data set distribution when redistributing data. Thus, an improvement of the algorithm is proposed and implemented in Thrill. Experiments along several scale factors and with several data sets are conducted and compared with the original Canonical Merge Sort algorithm. Results show similar overall performance and improvements in network communication on certain data sets. Finally, next steps for the newly developed algorithm are discussed.

Simultaneous Integer Flows

  • Datum: Fr, 4 Okt 2019, 14:30
  • Ort: SR 301
  • Vortragende(r): Emil Dohse, ITI Wagner; Bachelor's Thesis
  • Inhalt: Flow algorithms have important practical and theoretical applications. A recent trend in algorithmics is to look at simultaneous variants of well-known problems. In this thesis, simultaneous integer flows are examined. For a given family of graphs, some edges in common, and some individual ones, a simultaneous flow consists of a feasible flow for each graph of the family so that the flow is the same on all common edges. We start by comparing simultaneous flows to standard flows, to see that most structural properties, like augmenting paths or min-cut max-flow duality, do not seem to translate to simultaneous flows. We then consider the decisions problem SimFlow, that asks whether a simultaneous integer flow with a certain value exists. We show that SimFlow is NP-complete even with heavy restrictions to the flow networks, like the common network only consisting of a path. In addition to that, we show that there is no polynomial-time approximation algorithm for simultaneous flows with subexponential approximation factor. On the positive side, we prove that SimFlow is FPT in the number of common or individual edges.

Upward-Rightward-Prescribed Planarity

  • Datum: Fr, 4 Okt 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Vera Chekan, ITI Wagner; Bachelor's Thesis
  • Inhalt: We introduce and investigate a new planarity variant for directed graphs called upward-rightward-prescribed planarity. An upward-rightward-prescribed graph is a directed graph in which every edge is assigned either a u- or an r-label. Such a graph is called upward-rightward-prescribed planar if there exists a planar drawing in which each u-labeled edge is drawn y-monotonic and each r-labeled edge is drawn x-monotonic. This planarity variant is strongly related to upward planarity and windrose planarity. We show that testing graphs for upward-rightward-prescribed planarity is NP-hard even for single-source graphs and consider a restricted setting where the subgraph induced by the u-labeled edges is a biconnected spanning subgraph and the embedding of this subgraph is fixed. For this restriction, we provide a linear-time algorithm that decides if an upward-rightward-prescribed drawing exists and in the positive case, constructs such a drawing. This algorithm reduces upward-rightward-prescribed-planarity testing to windrose-planarity testing. We show that there exist upward-rightward-prescribed planar graphs that admit no straight-line drawing. The relation to windrose planarity implies that every upward-rightward-prescribed planar graph has an (upward-rightward-prescribed planar) drawing on a grid of polynomial size with at most three bends per edge.

Sommersemester 2019

Spaces of phylogenetic networks

  • Datum: Fr, 27 Sep 2019, 14:30
  • Ort: SR 301
  • Vortragende(r): Jonathan Klawitter, ITI Wagner; Guest from the University of Auckland
  • Inhalt: Phylogenetic networks are leaf-labelled graphs used to visualise evolutionary histories of species. Using rearrangement operations that make small graph-theoretical changes to transform one network into another one, we obtain a graph over a set of phylogenetic networks. In this talk I will present the results of my PhD work on such spaces of phylogenetic networks, including results on connectedness, the size of neighbourhoods, and shortest paths.

Local Ordered Covering Numbers

  • Datum: Fr, 27 Sep 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Laura Merker, ITI Wagner
  • Inhalt: Queue Number und Stack Number sind zwei Graphparameter, die in der Literatur viel untersucht wurden. Bei beiden Parametern wird ein Layout gesucht, das aus einer Knotenordnung und einer Partition der Kanten besteht, wobei bestimmte geordnete Subgraphen in keiner Teilmenge der Partition auftreten dürfen. Während klassischerweise die Größe der Partition minimiert wird, definieren wir eine lokale Variante der Parameter. Hierbei heißt ein Layout k-lokal, wenn jeder Knoten in höchstens k verschiedenen Teilmengen enthalten ist. Gesucht ist dann das kleinste k, sodass für einen gegebenen Graphen ein k-lokales Queue/Stack Layout existiert. Im Rahmen von Praxis der Forschung werden der Stand der Forschung, die geplanten Fragestellungen und eigene Vorarbeiten präsentiert.

Communication Optimization by Data Replication for Distributed Graph Algorithms

  • Datum: Fr, 27 Sep 2019, 10:00
  • Ort: SR 236
  • Vortragende(r): Tobias Ribizel, ITI Sanders; Master's Thesis
  • Inhalt: TBA

Drawing Hypergraphs as Metro Maps

  • Datum: Fr, 6 Sep 2019, 14:30
  • Ort: SR 301
  • Vortragende(r): Fabian Frank, ITI Wagner; Bachelor's Thesis
  • Inhalt: Eine Metromap-Darstellung eines Hypergraphen ist eine Visualisierung eines Hypergraphen in der jede Hyperkante des Hypergraphen als eine Metrolinie und jeder Knoten als eine Metrostation dargestellt wird. Eine Knotenkreuzung ist ein Knoten, in welchem sich mindestens zwei Metrolinien kreuzen. Ein path-based support Graph G für einen Hypergraphen H ist ein Graph, sodass für jede Hyperkante h von H ein Pfad existiert der in G liegt und genau die Knoten von h enthält. Für einen gegebenen Hypergraphen H = (V, E) und eine gegebene Ordnung jeder Hyperkante zeigen wir, dass es NP-vollständig zu entscheiden ist, ob eine Metromap-Darstellung des Hypergraphen mit höchstens k Kreuzungsknoten existiert, auch wenn die Einbettung bereits vorgegeben ist. Des Weiteren stellen wir einen polynomiellen Algorithmus für den Fall vor, dass die Einbettung vorgegeben und der zugehörige path-based support Graph ein Baum ist.

Engineering Overlapping Community Detection based on the Ego-Splitting Framework

  • Datum: Fr, 6 Sep 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Armin Wiebigke, ITI Wagner; Master's Thesis
  • Inhalt: A community is a set of strongly connected nodes in a network. In real-world networks, communities often overlap, meaning that nodes may be part of multiple communities. We evaluate the problem of detecting overlapping communities in a network, using the ego-splitting framework. The ego-splitting framework first searches for the communities of each node in its local neighborhood, the ego-net. Each node is then split into multiple personas to disentangle overlapping communities, each persona corresponding to one of the locally detected communities. The result is a persona graph with non-overlapping communities on which detecting communities is comparatively easy. The ego-splitting framework requires two non-overlapping community detection algorithms, one to analyze the ego-net and one to detect the global communities. While this means that the ego-splitting framework is highly flexible, there is a lack of practical evaluation. We present extensive experimental results for various non-overlapping community detection algorithms and analyze their usefulness in the framework. Our evaluation shows that choosing the right algorithms is essential to detect high quality communities. We extend the ego-splitting framework by three additional steps: We extend the ego-nets, connect the personas of each node, and clean up the detected communities. Our experiments show that our improved version of the ego-splitting framework is able to provide a higher quality than state-of-the-art algorithms on many synthetic graphs. Moreover, the running time of our algorithm is still comparatively low and does not depend on the structure of the network.

Distributed String Sorting Algorithms

  • Datum: Mi, 24 Jul 2019, 11:30
  • Ort: SR 236
  • Vortragende(r): Matthias Schimek, ITI Sanders; Master's Thesis
  • Inhalt: Although there has been extensive work on sequential and shared-memory parallel string sorting, the problem has not yet been thoroughly studied for distributed systems. In this thesis we present two new distributed string sorting algorithms. Our first algorithm dMSS extends the -- to our knowledge -- only distributed string sorting algorithm with longest common prefix-related optimizations. Furthermore, we present a new approach to compute an ordered partition of a distributed string array such that the number of characters in each set of the partition has about the same value. Our second algorithm dPDSS addresses a major problem of distributed string sorting: the communication of characters which are not required to establish a lexicographical order of the input. In dPDSS distributed bloomfilters are applied to approximately compute the distinguishing prefixes of the input without exchanging the actual strings. Afterwards, the algorithm operates on the (approximate) distinguishing prefixes only. By this means, a significant amount of communication can be saved provided that the distinguishing prefixes are short compared to the strings themselves. Furthermore, we introduce a new string generator producing string data sets with the ratio of the distinguishing prefix length to the entire string length being an input parameter. Our evaluation on up to 1280 processors shows that the presented algorithms clearly outperform their competitors on both generated and real-world data.

Customizable Contraction Hierarchies with Turn Costs

  • Datum: Fr, 19 Jul 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Michael Zündorf, ITI Wagner; Bachelor's Thesis
  • Inhalt: Many algorithms are known to solve the shortest path problem on road networks without turn costs. This work focuses on Customizable Contraction Hierarchies and extends this technique to handle networks with turn costs efficiently. We compare different ways to model turn costs in road networks and evaluate which impact those models have on the performance of Customizable Contraction Hierarchies. We also propose some improvements to handle turn costs faster. Albeit most of these improvements were designed for turn costs, some do also apply to Customizable Contraction Hierarchies in general. In addition to that, we introduce a new algorithm to build a Customizable Contraction Hierarchy which is not only simpler but also more efficient than the original algorithm.

A Comparative Study of Overlapping Community Detection Algorithms

  • Datum: Mi, 26 Jun 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): John Gelhausen, ITI Wagner; Bachelor's Thesis
  • Inhalt: Das Ziel der Erkennung von Communities in Netzwerken ist es, Gruppen von Knoten zu finden welche dicht zueinander und spärlich zu dem Rest des Netzwerkes verbunden sind. Überlappende Communities erlauben es den Knoten Teil mehrerer Communities zu sein. Wir evaluieren neun Algorithmen für die Erkennung von überlappenden Communities, indem wir sie mit Hilfe von Experimenten auf synthetischen Benchmark Netzwerken und realen Netzwerken miteinander vergleichen. Die Algorithmen werden empirisch evaluiert anhand von Performanz-Metriken welche die Ähnlichkeit der gefundenen Communities zu denen der Referenz Communities berechnen. Eine solche Metrik ist zum Beispiel die Normalized Mutual Information (NMI). Wir haben zusätzliche Experimente durchgeführt, um die Algorithmen detaillierter analysieren zu können. Zum Beispiel haben wir überprüft, ob die Algorithmen zu wenige oder zu viele, zu kleine oder zu große Communities finden. Unsere Resultate zeigen, dass OSLOM und MOSES am besten sind, um überlappende Communities zu finden, wobei OSLOM bessere Resultate auf kleinen Netzwerken und MOSES bessere Resultate auf größeren Netzwerken liefert. Unsere Resultate zeigen auch, dass es sehr wichtig ist ergänzende Metriken zu benutzen um die Qualität von den Algorithmen zu evaluieren. Qualitäts-Metriken, wie die NMI oder der Omega Index, berechnen nur die Gesamtqualität eines gefundenen Covers. Dagegen liefern uns ergänzende Metriken mehr Informationen über das Verhalten der Algorithmen. Schlussendlich, während einige Algorithmen gute Resultate auf synthetischen Netzwerken liefern, sind keine der Algorithmen in der Lage die Community Struktur in realen Netzwerken zu erkennen. Das kommt daher, dass die erkannten Communities grundlegend unterschiedlich von den Communities sind die durch Meta-Daten definiert sind.

Effiziente Planung „schöner“ Rundfahrten

  • Datum: Di, 4 Jun 2019, 13:00
  • Ort: SR 301
  • Vortragende(r): Sebastian Knapp, ITI Sanders; Master's Thesis
  • Inhalt: There is already a lot of work on calculating the shortest path from a starting point to a destination, and there are also algorithms for finding beautiful round trips. The aim of this work is to combine these two topics and to present algorithms which calculate beautiful round trips considering an intermediate destination and a distance specification. With solving this problem, on the one hand, significantly more beautiful round trips compared to a commercial third-party provider are found and on the other hand, running times of about 100 milliseconds for round trips of a distance of 200 kilometers are achieved using the acceleration techniques of the Contraction Hierachies method. In addition, it is shown that the algorithms also produce qualitatively similar results for longer distances at practical running times.

Transmission Network Expansion Planning for Curing Critical Edges

  • Datum: Fr, 17 Mai 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Lena Winter, ITI Wagner; Masters Thesis
  • Inhalt: In this thesis we discuss the problem to expand transmission networks with the objective to cure critical edges. Critical edges are hereby identified as edges in the transmission network, thats failure would lead to black outs. To identify critical edges we use in this thesis a method proposed by Witthaut et al. [WRZ+16a, WRZ+16b]. This method relies on an graph theoretical approach and can be applied independently from the underlying network model. First we define the problem to expand the transmission network with the objective to cure critical edges accurately. Then we discuss the complexity of the defined problem even for restricted instances of the problem. A major part of this thesis is the development and introduction of different approaches to solve this problem. We will introduce approaches using the underlying network model as well as heuristics solely relying on the graph theoretical simplification of the transmission network. After evaluating the proposed optimization methods we find that the simplification to approach the problem solely graph theoretical leads to large speed ups while retaining the result quality in most cases we tested.

Erweiterungsplanung in elektrischen Netzen mittels dynamischer Programmierung

  • Datum: Fr, 12 Apr 2019, 14:30
  • Ort: SR 301
  • Vortragende(r): Robert Mumper, ITI Wagner; Bachelor's Thesis
  • Inhalt: Durch die anhaltende Energiewende und den stätig steigenden Strombedarf der Verbraucher sind viele Stromnetze nicht mehr zeitgemäß oder werden in absehbarer Zukunft den Anforderungen nicht mehr entsprechen. Transmission Network Expansion Planning (TNEP) befasst sich unter anderem mit der Ermittlung optimaler Erweiterungen der aktuellen Stromnetze. In dieser Arbeit wird ein dynamischen Programm zur Lösung dieses Optimierungsproblems entwickelt. Da diese Arbeit eine theoretische Betrachtung zur Motivierung des Problems ist, wird lediglich die Klasse der serien-parallelen Graphen betrachtet. Als Referenz wird ein bekanntes Optimierungsprogramm herangezogen, mit dem die Ergebnisse und die Performance verglichen werden. Für alle betrachteten Eingaben liefert der vorgestellte Algorithmus optimale Ergebnisse. Die Laufzeiten des vorgestellten Algorithmus sind außer bei sehr kleinen Stromnetzen schlechter als die des Referenzprogramms.

Algorithmische Werkzeuge zur Analyse von Routingdaten basierend auf historischen Fahrzeugtrajektorien

  • Datum: Fr, 12 Apr 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Florian Krone, ITI Wagner; Bachelor's Thesis
  • Inhalt: Korrekte Routing-Services werden immer wichtiger, da sich immer mehr Menschen auf sie verlassen. Daher stellen wir in dieser Arbeit Algorithmen vor, die Routing-Services auf Fehler untersuchen. Die Fehler, die wir finden wollen, sind fehlende Straßen, verbotene Manöver und Abweichungen in der vorhergesagten Fahrtdauer. Dazu nutzen wir historische Fahrzeugtrajektorien. Unser Ansatz ist es, die Trajektorien nachzubilden, indem wir mit den Routingdaten, von Start bis Ziel der Trajektorie, eine Route berechnen. Zur Überprüfung der Nachbildung nutzen wir die Fréchet-Distanz. Durch die Identifizierung der Stellen, an denen die Nachbildung fehlschlägt, können wir mögliche Fehler in den Routingdaten finden. Wir schlagen eine Clustering-Strategie vor, um Punkte herauszufiltern, an denen die Nachbildung durch GPS-Ausreißer oder irrationales Verhalten des Fahrers nicht möglich ist. Dadurch identifizieren wir Punkte, an denen Fehler in den Routingdaten wahrscheinlich sind. Zusätzlich haben wir auf Basis der Zwischenergebnisse unseres Algorithmus Maßzahlen entwickelt, die einen Vergleich der Qualität verschiedener Routing-Services ermöglichen.

A Brief Introduction to Cycle Bases and Matroids

  • Datum: Mi, 10 Apr 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Torsten Ueckerdt, ITI Wagner
  • Inhalt: Roughly speaking, a cycle basis of a graph G is a set of cycles that generates all cycles in G; an important case being a generation in terms of linear combinations over a field Q. Roughly speaking, a matroid of a ground set U is a set of subsets of U that is downwards-closed and always allows greedy extension to a maximum size subset; an important case being linear independent vectors in a vector field, as well as, acyclic subgraphs of a graph. In this talk, we seek to give a gentle introduction to both, cycle bases and matroids, trying to highlight some of their interconnections.

Concurrent Dynamic Quotient Filters - Packing fingerprints into atomics

  • Datum: Di, 9 Apr 2019, 14:30
  • Ort: SR 301
  • Vortragende(r): Robert Williger, ITI Sanders; Master's Thesis
  • Inhalt: Quotient filters are approximate membership data structures that can be used for a variety of applications, from speeding up database accesses to uses in computational biology. We look at several improvements to common quotient filters which are orthogonal to each other and can be combined as needed. We show how to use compact arbitrary length data types to reduce the memory usage by up to seven times and get very close to the theoretical optimum. We also present two different approaches to building concurrent quotient filters that use localized locking or no locking at all. This leads to a good linear speedup with increasing thread counts and an increase in performance of up to four times compared to traditional locking techniques. Additionally, we describe how to use a multilevel quotient filter structure to implement dynamic growing while still allowing for a user defined maximum false positive rate and being less than 10% slower compared to nongrowing variants.

Kompressionstechniken für Beschreibungen von SAT Formeln

  • Datum: Di, 9 Apr 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Jens Manig, ITI Sanders; Bachelor's Thesis
  • Inhalt: In dieser Arbeit werden verschiedene Ansätze zur Kompression des DIMACS-Dateiformats für aussagenlogische Formeln vorgestellt. Das DIMACS-Dateiformat findet beim SAT-Solving Verwendung und enthält logische Klauseln welche als Zahlen repräsentiert, aber als Strings gespeichert werden. Daher beschäftigt sich die vorliegende Arbeit damit, Vorwissen über dieses Format für die Kompression zu verwenden. Der erste entwickelte Ansatz ist eine Umwandlung der Strings in Zahlen mit einer festen Anzahl Bytes pro Zahl, der zweite Ansatz extrahiert die Vorzeichen in Bitvektoren und nutzt eine variable Byteanzahl pro Zahl, der dritte nutzt einen Move-to-Front Ansatz, der vierte erreicht zusätzliche Kompression über Präfixmatching aufeinanderfolgender Zeilen und der letzte Ansatz ist eine Kombination aus Move-to-Front und Präfixmatching. Von den vorgestellten Ansätzen ist die Kombination die beste bezüglich des Kompressionsfaktors. Bei der Laufzeit ähneln sich die entwickelte Ansätze stark, sowohl in der Kodierung als auch Dekodierung. Im Vergleich zum allgemeinen ZIP-Kompressionsverfahren ist die Kodierungszeit bedingt besser, während die Dekodierungszeiten von ZIP noch deutlich geringer sind. Beim Kompressionsfaktor ist die Kombination nicht weit von ZIP entfernt, und eine Kombination aus ZIP und den vorgestellten Verfahren führt zu den insgesamt besten Kompressionsraten.

Algorithms for the Pagination Problem on Public Transit Networks

  • Datum: Fr, 5 Apr 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Moritz Halm, ITI Wagner; Bachelor's Thesis
  • Inhalt: Diese Arbeit beschäftigt sich mit der Frage, wie Reiseprofile auf öffentlichen Verkehrsnetzwerken unter Einsatz von Paginierung berechnet werden können. Paginierung bedeutet hier das Aufteilen eines Profiles in Abschnitte (Seiten), die nacheinander berechnet und ausgegeben werden. Dabei hat die Sortierung der Reisen innerhalb eines Profils entscheidenden Einfluss auf die Nützlichkeit des Ergebnisses. Wir vergleichen Sortierungen von Reisen nach Ankunfts- und Abfahrtszeit, und schlagen außerdem vor, Reisen nach dem frühesten Zeitpunkt, von dem an sie optimal sind, zu sortieren. Wir stellen verschiedene auf dem RAPTOR-Algorithmus basierende Ansätze vor, wie Reisen in einer jeder dieser Sortierungen entsprechenden Reihenfolge berechnet werden können. Zunächst beschreiben wir, wie der von Wagner und Zündorf (2017) vorgestellte Profilalgorithmus jede dieser Sortierungen liefert, wenn man die Reihenfolge der durchgeführten Vorwärts- und Rückwärtssuchen in geeigneter Weise anpasst. Speziell für die Sortierung nach Ankunftszeit, können allerdings kürzere Laufzeiten durch den Einsatz von rRAPTOR erreicht werden, indem man den Algorithmus auf einem umgekehrten Netzwerk ausführt. Für die anderen beiden Sortierungen erreichten wir leichte Geschwindigkeitsvorteile durch eine Kombination beider Ansätze. Wir haben die Laufzeit unserer Algorithmen anhand von Experimenten auf dem öffentlichen Verkehrsnetzwerk der Schweiz gemessen.

On Rigidity of Graphs

  • Datum: Mo, 1 Apr 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Oliver Suchan, ITI Wagner; Bachelors Thesis
  • Inhalt: A rigid framework refers to an embedding of a graph, in which each edge is represented by a straight line. Additionally, the only continuous displacements of the vertices, that maintain the lengths of all edges, are isometries. If the edge lengths are allowed to only be perturbed in first order, the framework is called infinitesimally rigid. In this thesis the degrees of freedom of a certain, new type of rigidity, called edge-x-rigidity, for a given framework in the 2-dimensional Euclidean space are examined. It does not operate on the length of an edge, but on the intersection of an edge's support line and the x-axis. This may then help to determine the class of graphs where every edge intersection with the x-axis can be repositioned along the x-axis, such that there still exists a framework that satisfies these position constraints

Wintersemester 2018

A specialized model for optimized memory consumption of time-dependent Contraction Hierarchies

  • Datum: Di, 26 Mär 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Sebastian Schmidt
  • Inhalt: Zeitabhängige Routenplanung wird momentan praktikabel, da mehr und mehr GPS-Daten über Autofahrten verfügbar werden. Aber die Nutzung von detaillierteren Daten für Zeitabhängige Routenplanung führt auch zu höherem Speicherverbrauch für Beschleunigungstechniken. Wir optimieren den Speicherverbrauch von Zeitabhängigen Customizable Contraction Hierarchies. Dazu stellen wir ein Optimierungsschema für die Eingabefunktionen vor, um den Speicherverbrauch der exakten TDCCH auf den optimierten Eingabedaten zu verringern. Wir argumentieren, dass unser Gewichtsoptimierungsschema nur sehr kleine signifikante Fehler einfügt, und größtenteils unter dem Rauschen in den Eingabedaten bleibt.


  • Datum: Fr, 22 Mär 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): -, ITI Wagner / PSE-Abschlussvorträge
  • Inhalt: Das Thema der PSE-Gruppen ist der Campus-Routenplaner.

Recognizing Planar Laman Graphs

  • Datum: Fr, 22 Feb 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Jonathan Rollin, ITI Wagner; Guest from the FernUni Hagen
  • Inhalt: Laman graphs are the minimally rigid graphs in the plane and can be characterized in geometric as well as combinatorial ways. We present two algorithms for recognizing planar Laman graphs. A simple algorithm with running time O( n^(3/2) ) and another one with running time O(n log^3 n) based on latest planar network flow algorithms. Both improve upon the previously fastest algorithm for general graphs by Gabow and Westermann [Algorithmica, 7(5-6):465--497, 1992] with running time O(n (n log n)^(1/2) ). Joint work with Lena Schlipf and André Schulz.

Ridesharing with Multiple Riders

  • Datum: Fr, 15 Feb 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Oliver Plate, ITI Wagner; Masters Thesis
  • Inhalt: Ridesharing bezeichnet die gemeinsame Nutzung eines Fahrzeuges für den Transport von Personen. Die wesentlichen Ziele dabei sind ökonomisch (Kosten teilen) als auch ökologisch (Reduzieren der Umweltbelastung). Das Thema meiner Arbeit ist die Realisierung von Mitfahrgelegenheiten, indem Anfragen zu den vorhandenen Angeboten zugeordnet werden. Der Themenkreis ist bereits in vielen Arbeiten mit unterschiedlichen Schwerpunkten untersucht worden, dazu geben wir einen Überblick mit diversen Klassifikationen, Optimierungszielen und Lösungsansätzen. Die vorliegende Arbeit befasst zuerst mit der Version, in der ein Fahrer Mitfahrgelegenheiten für eine oder mehrere Personen entlang einer von ihm zu fahrenden Route anbietet, wobei gewisse Umwege in Kauf genommen werden. Dazu wird ein Algorithmus vorgestellt, der auf einer schnellen und dynamischen Lösung für one-to-many (many-to-one) Kürzeste-Wege-Anfragen aufbaut und somit rechenintensive einzelne Kürzeste-Wege-Anfragen umgeht. Dabei wird die Bestimmung kürzester Pfade mithilfe einer Kombination aus Bucket-Einträgen und Contraction Hierarchies durchgeführt. Zudem werden, mit Blick auf die Antwortzeiten von Anfragen, zusätzliche Strategien zur Beschleunigung eingeführt. Die Flexibilität unseres Lösungsansatzes wird gezeigt, indem mit geringer Abänderungen auch das sogenannte Taxi-Ridesharing-Problem angegangen wird. Verschiedene Messungen hinsichtlich Antwortzeiten, Trefferquoten und der Qualität der Treffer dienen dazu, die Qualität der erstellten Lösung zu untersuchen und Vergleiche mit anderen Lösungsverfahren anzustellen.

Collinearity of Independent Sets - Algorithmic Challenges

  • Datum: Mo, 14 Jan 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Almut Demel, ITI Wagner; Masters Thesis
  • Inhalt: A subset $S \subset V(G)$ of vertices of a planar graph G is called collinear if G admits a plane straight-line drawing where all the vertices in S lie on a line. The aim of this thesis is to find a lower bound for the maximal number of collinear vertices in graphs of a certain graph class. Our approach is to examine whether independence or a fixed minimal distance between vertices in a subset of vertices is a sufficient condition for collinearity. An independent set of vertices with minimal pairwise distance d is called d-scattered. The size of maximum independent sets is linear in the number of vertices in planar graphs. However, in general planar graphs the number of collinear vertices is limited by a sublinear upper bound. Thus we examine specific graph classes, in particular series-parallel graphs and 4-connected triangulations. For the former we show that any fixed minimal pairwise distance between vertices of an independent set is not a sufficient condition for collinearity. Though we introduce a meaningful subclass of series-parallel graphs, in which 3-scattered sets are always collinear. For 4-connected triangulations we show that independent sets are in general not collinear and present forbidden substructures. We further present approaches to prove collinearity of d-scattered sets and outline the limits of these approaches.

Route Planning with Temporary Road Closures

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

Dynamische Baumkompression mit Top Trees

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

Optimierung globaler Flexibilität von elektrischen Lasten mittels Genetischer Algorithmen

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

A Flow-Based Initial Partitioning Algorithm for Multilevel Graph Partitioning

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

Distributed Kernelization for Independent Sets

  • Datum: Di, 11 Dez 2018, 13:00
  • Ort: SR 301
  • Vortragende(r): Tom George, ITI Sanders; Bachelors Thesis
  • Inhalt: To appear.

A Practical Analysis of Kernelization Techniques for the Maximum Cut Problem

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

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

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

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

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

PoI Anfragen im Vergleich

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

Dijkstra-basiertes Mapmatching

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

Kernelization for Maximum Weight Independent Sets and Distributed Connected Components

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

Parallelization Techniques for Customizable Contraction Hierarchies

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

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

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

Relaxed Priority Queues: Using buffers to guarantee quality

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

Local Page Numbers

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

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

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

Verkabelung von Windfarmen auf Bäumen

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

Sommersemester 2018

Wind Farm Cabling using Spectral Clustering

  • Datum: Di, 18 Sep 2018, 14:30
  • Ort: SR 301
  • Vortragende(r): Niklas Fuhrberg, ITI Wagner; Bachelors Thesis

Drawing a Level Planar Graph with Fixed Slopes

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

Parallel Greedy Graph Matching

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

Hierarchical Task Network Planning using SAT Techniques

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

Support Vector Machines via Multilevel Label Propagation

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

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

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

Partial Contraction Hierarchies

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

Transmission Network Expansion Planning using the Railway Network

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

Parallelizing Graphplan

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

Faster Public Transit Routing with Unrestricted Walking

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

On Aesthetic Functions in Visualizations of Text Variant Graphs

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

Load-Balancing for parallel Delaunay Triangulations

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

Beobachtungen des Maximalen Flexiblen Drehstromübertragungssystem Flusses

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

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

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

Wintersemester 2017

Hypergraph Clustering

  • Datum: Do, 29 Mär 2018, 14:00
  • Ort: SR 301
  • Vortragende(r): Hrudaya Ranjan Sahoo, IIT Matras; Masters Thesis Progress Report
  • Inhalt: To appear.

Communication-free Massively Distributed Graph Generation

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

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

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

On Ortho-Radial Drawings for Metro Networks

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

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

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

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

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

Aligned Drawing of Plane Level Graphs

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

A Unified Framework for Electric Vehicle Routing

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


  • Datum: Fr, 8 Dez 2017, 14:00
  • Ort: SR 301
  • Vortragende(r): Reserviert von Herrn Griesbaum, Reserviert von um 14 Uhr bis um 15:30 Uhr
  • Inhalt: -

Constructing Cuckoo hash tables independent of their load-factor

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

A Practical, Compact Representation for Plane Triangulations

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

On the Complexity of Public Transit Profile Queries

  • Datum: Mo, 13 Nov 2017, 13:30
  • Ort: SR 236
  • Vortragende(r): Florian Grötschla, ITI Wagner; Bachelors Thesis
  • Inhalt: TBA

Optimierung von Routen für spontane Zieländerung

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

Graph-theoretical Characterizations of Metropolitan Areas

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

Tracking of Communities in Social Networks

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

Engineering Multimodal Transit Route Planning

  • Datum: Fr, 10 Nov 2017, 13:30
  • Ort: SR 301
  • Vortragende(r): Huyen Chau Nguyen, ITI Wagner; Masters Thesis
  • Inhalt: TBA

Sparsity and Dimension

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

Extending drawings with fixed inner faces with and without bends

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

Engineering FPT-based Edge Editing Algorithms

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

Smart Local Search in Hypergraph Partitioning

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

Optimal Route Planning for Hitchhiking

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

On Interval Planar Graphs

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

Sommersemester 2017

An Optimal Algorithm for Approximate Minimum Selection with Unreliable Comparisons

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

Peak Demand Scheduling For One Resource

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

Clusteringansätze von Windfarmen

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

Incremental SAT Solving for SAT Based Planning

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

Drawing graph with high crossing resolution

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

Task Mapping in a Distributed Setting

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

Ant-based Algorithms for the Wind Farm Cable Layout Problem

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

Entwicklung eines genetischen Algorithmus zur effizienten Verkabelung von Windfarmen

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

Engineering Distributed Graph Clustering using MapReduce

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

Simultane Kreissehnengraphen

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

Drawing Planar GitHub Network Graphs

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

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

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

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

  • Datum: Di, 23 Mai 2017, 16:00
  • Ort: Seminarraum 228 im Geb. 10.91.
  • Vortragende(r): 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

  • Datum: Di, 23 Mai 2017, 13:00
  • Ort: SR 301
  • Vortragende(r): 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

  • Datum: Fr, 19 Mai 2017, 14:00
  • Ort: SR 301
  • Vortragende(r): 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

  • Datum: Do, 11 Mai 2017, 14:00
  • Ort: Gebäude 50.31, Bauingenieure Hörsaal 107, Gotthard-Franz-Str. 3, 76131 Karlsruhe
  • Vortragende(r): 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

  • Datum: Di, 9 Mai 2017, 13:00
  • Ort: SR 301
  • Vortragende(r): 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

  • Datum: Di, 2 Mai 2017, 13:00
  • Ort: SR 301
  • Vortragende(r): 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

  • Datum: Di, 25 Apr 2017, 13:00
  • Ort: SR 301
  • Vortragende(r): 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

  • Datum: Mi, 19 Apr 2017, 13:00
  • Ort: SR 301
  • Vortragende(r): 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.
  • Datum: Mi, 5 Apr 2017, 13:30
  • Ort: SR 301
  • Vortragende(r): 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

  • Datum: Mi, 5 Apr 2017, 13:00
  • Ort: SR 301
  • Vortragende(r): 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.