Institut für Theoretische Informatik, Algorithmik

Forschungsseminar

Wintersemester 2020

Multicriteria Trip-Based Public Transit Routing

  • Datum: Fr, 15 Jan 2021, 14:30
  • Ort: MS teams
  • Vortragende(r): Moritz Potthoff, ITI Wagner; Bachelor Thesis
  • Inhalt: Der Trip-Based Public Transit Routing Algorithmus berechnet Pareto-optimale Routen in öffentlichen Verkehrsnetzwerken für zwei Kriterien: früheste Ankunftszeit und minimale Anzahl Umstiege. Diese Arbeit erweitert den Algorithmus, um Pareto-optimale Routen für ein zusätzliches Kriterium zu berechnen. Der Walking Trip-Based Algorithmus minimiert zusätzlich die Fußwegezeit entlang einer Route. Der Fare Zone Trip-Based Algorithmus optimiert Routen zusätzlich für die minimale Menge an genutzen Tarifzonen. Dazu werden sowohl die Vorberechnungs- als auch die Anfragephase des Algorithmus angepasst und optimiert. Die entstandenen Algorithmen werden ausführlich auf drei realen öffentlichen Verkehrsnetzen evaluiert und Anfragelaufzeiten werden mit denen von McRAPTOR vergleichen. Der Walking Trip-Based Algorithmus berechnet Anfragen auf allen Netzwerken schneller als der McRAPTOR Algorithmus. Die erreichte Beschleuningung gegenüber McRAPTOR liegt zwischen 1.18 und 3.47. Die parallelisierte Vorberechnung läuft für kleine Netzwerke in Minuten und braucht für eine komplexe Variante der Schweiz nur 36 min. Die zweite Erweiterung, der Fare Zone Trip-Based Algorithmus, ist deutlich langsamer als die McRAPTOR-Variante. Basierend auf diesen Erkenntnissen wird analysiert für welche Kombinationen von Optimierungskriterien der multikriterielle Trip-Based-Ansatz vielversprechend ist und mögliche Integrationen mit anderen Algorithmen werden diskutiert.

Evaluating Wind Farm Cable Layouts obtained from Negative Cycle Canceling using Power Flow Analysis in eASiMOV

  • Datum: Do, 17 Dez 2020, 14:00
  • Ort: TBD
  • Vortragende(r): Pascal Mehnert, ITI Wagner; Bachelor Thesis
  • Inhalt: In an offshore wind farm the electrical energy generated by each wind turbine needs to be transported to an offshore substation, to make it available to the rest of the grid. It is the responsibility of the internal cabling of such a wind farm to connect each wind turbine, possible via other turbines, to a substation. The Wind Farm Cabling Problem (WCP) formalizes the design of internal cable layouts as a flow problem on graphs and defines a criteria for their optimality, in the form of a cost function. A number of algorithms have been proposed in the literature to solve instances of WCP, of which we focus mainly on the Negative Cycle Canceling (NCC) heuristic. In this thesis we evaluate cable layouts obtained from NCC and other algorithms, using the capabilities of power flow analysis. We introduce a software application that allows us to generate the required simulation models for any cable layout and calculate power flows for them. The calculation results allow us to gain insight into some of the operating characteristics of the cable layouts. We use this in particular to assess if certain structures in cable layouts, like cycles between multiple turbines, have negative effects on the performance of the resulting simulation models. In the course of this thesis we also compare a number of variations of NCC in terms of the efficiency of solutions generated by them.

Communication-free Generation of Graphs with Planted Communities

  • Datum: Fr, 11 Dez 2020, 15:00
  • Ort: online
  • Vortragende(r): Adrian Feilhauer, ITI Wagner/Sanders; Master Thesis
  • Inhalt: Graphen, die soziale Strukturen widerspiegeln, beinhalten oft sogenannte Communities von Knoten, deren Mitglieder untereinander häufig verbunden sind. Algorithmen, die derartige Netzwerke analysieren, sind zur Qualitätskontrolle auf Graphen mit bekannter Communitystruktur angewiesen. Hier werden einige Modelle mit zugehörigen Generatoren vorgestellt, die Graphen mit spezieller Communitystruktur erzeugen. Die Generatoren arbeiten in verteilten Systemen ohne Kommunikation. Dadurch können Graphen generiert werden, ohne von Beschränkungen der Kommunikation zwischen Prozessoren beeinträchtigt zu werden. Die einfacheren Modelle skalieren nahezu perfekt. Mit 128 Kernen können dort Graphen mit 2^31 Knoten und über 2^42 Kanten in weniger als zehn Minuten erzeugt werden. Das entspricht ca. 10^8 Kanten pro Sekunde und Prozessor. Komplexere Modelle mit nach Potenzgesetz verteilten Communitygrößen und Knotenmitgliedschaften skalieren einigermaßen gut. Obwohl die Verteilung der Last zwischen den verwendeten 128 Kernen suboptimal war, konnten für Graphen mit 2^25 Knoten durchschnittlich 10^6 Kanten pro Sekunde und Prozessor generiert werden.

Negative Cycle Canceling for Cost-Efficient Wind Farm Planning

  • Datum: Fr, 11 Dez 2020, 14:00
  • Ort: TBD
  • Vortragende(r): Alina Valta, ITI Wagner; Bachelor Thesis
  • Inhalt: TBA

Ordered Covering Numbers

  • Datum: Fr, 27 Nov 2020, 14:00
  • Ort: ms teams
  • Vortragende(r): Laura Merker, ITI Wagner; Master Thesis
  • Inhalt: Given a graph, we aim to find a vertex ordering and a partition of the edges such that each part satisfies certain conditions like being crossing-free. We first discuss results and open problems for some ordered covering numbers (including variants of page numbers, queue numbers, and track numbers) and then focus on book embeddings of upward planar graphs. A directed acyclic graph is called upward planar if it admits a plane drawing such that all edges increase monotonically in y-direction. A book embedding of an upward planar graph consists of a topological ordering of the vertices and a partition of the edges into pages, where two edges whose endpoints form an ABAB-pattern may not belong to the same page. That is, each page is crossing-free if the vertices are placed on a straight line and all edges are drawn in the same half-plane. The page number of a graph G is defined as the smallest k such that there is a book embedding with at most k pages for G. We show that there is an upward planar graph (and even a planar poset) that requires at least five pages.

Engineering an algorithm for optimal backload allocation in freight exchanges

  • Datum: Mi, 11 Nov 2020, 10:00
  • Ort: i10 Jitsi
  • Vortragende(r): Julian Labeit, ITI Sanders; Master Thesis
  • Inhalt: In this work we examine a specific problem that occurs when trucking companies search for matching orders in so called freight exchanges. The objective is to find the cheapest route for a truck from a start s to a destination t while executing additional orders from the freight exchange along the way. First, we model this problem as a shortest-path problem in a graph with O(n) vertices, negative edge weights and possibly negative cycles. Second, we apply proposed algorithms for the Longest Paths problem and from the Vehicle Routing Problem with Profits. Finally, we present an evaluation of the different approaches on real example datasets from the logistics field.

On the Strong Product Theorem -- Improving the Treewidth Bound

  • Datum: Di, 10 Nov 2020, 13:00
  • Ort: MS Teams
  • Vortragende(r): Wendy Yi, ITI Wagner; Bachelor Thesis
  • Inhalt: A layering of a graph assigns each vertex an integer such that layers of adjacent vertices differ by at most one. A path in a graph with a given layering is vertical if its vertices are assigned pairwise distinct layers. Dujmovic et al. recently proved the Strong Product Theorem, which states that for every planar graph G with a BFS-layering (a type of layerings that are based on distances in BFS-trees), the vertices of G can be partitioned into vertical paths P such that the quotient graph G/P has treewidth at most 8. This is equivalent to the statement that every planar graph is a subgraph of the strong product of some graph with treewidth at most 8 and some path. By modifying the original proof of the Strong Product Theorem, we prove that the upper bound for the treewidth of the quotient graph can be improved to 7. Additionally, we show that this bound is tight when following the approach from the proof. Moreover, we prove that for a particular subclass of planar graphs, we can obtain a better upper bound.

Accurate Public Transit Assignment using Network Pruning and Quasi-Monte Carlo Simulation

  • Datum: Fr, 6 Nov 2020, 14:00
  • Ort: SR 301
  • Vortragende(r): Kolja Kühn, ITI Wagner; Bachelor Thesis
  • Inhalt: We study the problem of computing traffic assignments for public transit networks. Given a list of passengers (each having an origin, a destination and a departure time), we want to predict for each passenger which journey they will take. This information allows us to estimate the expected utilization of each vehicle. Previous work accounted for variations in the passengers' preferences by adding a randomly distributed error term to the utility of each possible journey. However, this model does not account for correlations between journeys that share connections or use vehicles of the same type (bus, tram etc.). We address this problem by weighting the time spent in each vehicle type by a randomly distributed factor. In this model journeys using the same vehicle type will automatically be correlated as they share the same factor. However, we show that computing an exact solution for this new problem is #P-hard. In order to provide an efficient algorithm for approximating a solution, we use a sampling-based algorithm and improve convergence by sampling using a low discrepancy point set. An assignment of all passengers travelling to the same destination can be computed with a single sweep over the network based on the Connection Scan Algorithm, resulting in an algorithm that scales well even with a large number of passengers. We present three pruning methods to further improve performance by reducing the size of the network during the assignment process.

Negative Cycle Canceling for the Wind Farm Cabling Problem with Distribution Nodes

  • Datum: Di, 27 Okt 2020, 14:00
  • Ort: TBD
  • Vortragende(r): Niklas Meier, ITI Wagner; Bachelor Thesis
  • Inhalt: Das Windfarm-Verkabelungsproblem (WCP) beschreibt die Aufgabe, eine Verkabelung einer Windfarm zu finden. Ziel des WCP ist es, dass von Turbinen produzierter Strom möglichst kostengünstig zu Substationen geleitet wird. Hierfür können unterschiedliche Kabeltypen genutzt werden, jeweils mit einer bestimmten Kapazität und unterschiedlichen Kosten. Dadurch ist das WCP im Allgemeinen NP-schwer. Als NP-schweres Problem gibt es keinen Algorithmus, der WCP effizient bis zum Optimalwert lösen kann, aber es gibt heuristische Ansätze, welche schnell eine angenäherte Lösung finden, wie zum Beispiel Negative Cycle Canceling (NCC). In meiner Arbeit wurde das WCP um Verteilerstationen erweitert. Verteilerstationen sind zusätzliche optionale Knoten, welche genutzt werden können, um elektrischen Fluss umzuleiten. Wird eine Verteilerstation genutzt, entstehen zusätzliche Kosten, welche die Baukosten der Verteilerstation repräsentieren. Ziel meiner Arbeit war es, einen vorhandenen NCC-Algorithmus so zu erweitern, dass er Verteilerstationen mit ihren entsprechenden Kosten berücksichtigen kann. Hierfür habe ich zunächst eine Fluss-Formulierung von WCP erweitert. In einem weiteren Schritt habe ich Verteilerstationen mit ihren entsprechenden Kosten in einem Residualgraphen modelliert. Dieser Residualgraph repräsentiert die Kosten von Flussänderungen und wird von dem NCC-Algorithmus genutzt. In einem dritten Schritt habe ich die Residualgraph-Modellierung algorithmisch realisiert und den vorhandenen NCC-Algorithmus angepasst.

Combining Multiple Criteria in Multi-Modal Route Planning using ULTRA

  • Datum: Fr, 9 Okt 2020, 15:00
  • Ort: SR 301
  • Vortragende(r): Manuel Schweigert, ITI Wagner; Master Thesis
  • Inhalt: We study the problem of finding multimodal, multicriteria journeys in transportation networks, including a single mode of unrestricted individual transport like walking, cycling or driven, and a schedule-based public transportation system. We use the ideas of the ULTRA preprocessing technique (UnLimited TRAnsfers) and combine them with a multicriteria search based on RAPTOR to produce full Pareto sets of optimal journeys. We examine the performance of this technique to optimize for three criteria: arrival time, walking distance and number of rides on public transportation vehicles utilized and show that this approach leads to a significant speed up for queries using these criteria for transfer speeds up to driving-speeds compared to other algorithms. Furthermore, they also show that the technique is well suited for metropolitan areas, but that it can also deal with country-scale networks.

UnLimited TRAnsfer Shortcuts with Delay Tolerance for Multi-Modal Journey Planning

  • Datum: Fr, 9 Okt 2020, 14:30
  • Ort: SR 301
  • Vortragende(r): Dominik Bez, ITI Wagner; Bachelor Thesis
  • Inhalt: Some routing algorithms for public transit assume that all vehicles (buses, trains, planes, etc.) depart and arrive on time, which is not a realistic scenario. This is especially true for algorithms which precompute data relying on the timetable. One such algorithm is ULTRA. ULTRA precomputes transfer shortcuts between stops of the public transit network to prepare public transit routing algorithms like RAPTOR for multi-modal scenarios which include a secondary mode of transportation (e.g., walking or cycling). These shortcuts represent a transfer between leaving a public transit vehicle and entering another. However, if the departure or arrival of a public transit vehicle is delayed, other shortcuts not precomputed by ULTRA may become necessary. The purpose of this thesis is to adapt ULTRA to a more realistic model of public transit that includes delays. The result is called DB-ULTRA and precomputes shortcuts for all possible delay scenarios within given bounds. These shortcuts can then be used by public transit routing algorithms to find optimal journeys even in those delay scenarios. We evaluate our new algorithm on the public transit networks of Switzerland and Germany and conclude that the query times are similar to ULTRA, as long as the maximum allowed delay is not too large. If both departures and arrivals can be delayed, a maximum delay of ten minutes yields half the query times of comparable multi-modal routing algorithms, whereas if only arrivals can be delayed, even a maximum delay of 30 minutes yields similar results.

Parallel FlowCutter Refinement for Hypergraph Partitioning

  • Datum: Fr, 9 Okt 2020, 14:00
  • Ort: SR 301
  • Vortragende(r): Florian Grötschla, ITI Wagner; Master Thesis
  • Inhalt: The balanced k-way hypergraph partitioning problem (HGP) has usages in a wide array of applications where performance is critical. Most partitioners use multilevel schemes that coarsen the hypergraph, find an initial partitioning and apply refinement algorithms while iteratively uncoarsening the hypergraph again. FlowCutter is a flow-based algorithm that uses the max-flow-min-cut theorem to find small cuts between blocks of the partition by solving a sequence of flow problems. This thesis presents parallelizations of flow algorithms that can be used in the weighted HyperFlowCutter framework (WHFC), an adaption of FlowCutter, that works for weighted hypergraphs, as well as an algorithm to extract smaller hypergraphs around an existing cut that are used as the input for the flow-based refinement. We also explore two approaches for parallel partitioning algorithms that use the fast sequential partitioner PaToH to find initial partitions and apply the flow-based refinement in parallel. One of them uses recursive bisection to split the hypergraph into increasingly smaller blocks, the second algorithm uses an initial k-way partition and schedules block pairs for parallel refinement steps. We conclude with an analysis of the algorithms in an experimental evaluation of our implementation. We show that our parallelized WHFC implementation provides good speed-ups and the sequential implementation of our Push-Relabel flow algorithm outperforms the existing Dinic implementation. The parallel refinement profits from the utilization of the parallel extraction and flow algorithms, resulting in a partitioner that scales well.

Approximating One-Sided Crossing Minimization with Graph Networks

  • Datum: Do, 8 Okt 2020, 14:00
  • Ort: SR 301
  • Vortragende(r): Thomas Weidmann, ITI Wagner; Bachelor Thesis
  • Inhalt: Zu einem gegeben Graphen existieren viele verschiedene Zeichnungen. In manchen Zeichnungen kann man die Beziehungen zwischen den Knoten besser erkennen als in anderen. Ein Merkmal einer guten Zeichnung eines Graphen ist die Anzahl an Kreuzungen der Kanten. Das zugehörige Optimierungsproblem heißt Kreuzungsminimierungsproblem (KMP) welches NP-schwer ist. Das einseitige Kreuzungsminimierungsproblem (EKMP) ist eine stark eingeschränkte Version davon wobei die Knoten auf zwei horizontale Linien aufgeteilt sind und gesucht ist eine Permutation der Knoten auf der oberen Linie, sodass die Anzahl der Kreuzungen minimal ist. Auch dieses Problem ist NP-schwer. Es existieren einige lang erforschte Heuristiken und wir versuchen zwei Heuristiken mit Hilfe von maschinellem Lernen zu entwickeln. Ein Ansatz startet in einer zufälligen Permutation und tauscht benachbarte Knoten um die Anzahl an Kreuzungen zu minimieren und in dem anderen Ansatz bestimmen wir den linkesten Knoten der Permutation und durch mehrfaches Anwenden dieses Vorgehens können wir eine komplette Permutation aufbauen. Wir konnten konkurrenzfähige Ansätze zu existierenden Heuristiken entwickeln, die auch auf größeren Instanzen als die Trainingsdaten (bis zu 20 Knoten) noch gut skalieren.

Sommersemester 2020

P_n-free colorings of planar graphs

  • Datum: Fr, 25 Sep 2020, 14:00
  • Ort: SR 301
  • Vortragende(r): Miriam Goetze, ITI Wagner; Bachelor Thesis
  • Inhalt: Axenovich et al. started the study of planar avoidable graphs. We say that a graph H is k-planar unavoidable if there exists a planar graph G such that every k-edge-coloring of G contains a monochromatic subgraph isomorphic to H, otherwise we call H k-planar avoidable. Similarly, we define the notion of k-outerplanar avoidable graphs. Axenovich et al. were in particular interested in 2-edge-colorings and showed that every path is 2-planar unavoidable. Building on their work, we continue the study of edge-colorings of planar graphs that do not contain a monochromatic path of a given length. Modifying a proof of Ding et al., we prove that paths of length at least 3 are 3-outerplanar avoidable and applying a result of Merker and Postle that there exists a natural number n such that paths of length at least n are 4-planar avoidable. Further, we study edge-colorings of the iterated triangulation, a specific family of planar graphs, that avoid a restricted class of long paths. Finally, we are interested in the complexity of the associated decision problem: Given a planar graph and a natural number k, is there a 3-edge-coloring that does not contain a monochromatic P_k? We attack the special case k = 2 by considering 3-regular, bridgeless, planar supergraphs.

Inclusion-Minimal Quasi-Threshold Editing

  • Datum: Fr, 18 Sep 2020, 14:30
  • Ort: SR 301
  • Vortragende(r): Luise Häuser, ITI Wagner; Bachelor Thesis
  • Inhalt: A graph is called a quasi-threshold graph if and only if it contains neither a path nor a cycle of length 4 as an induced subgraph. The quasi-threshold editing problem is concerned with the question, how to construct a quasi-threshold graph from an arbitrary graph by inserting or deleting as few edges as possible. This problem is NP-hard. Here we present an algorithm which determines an inclusion-minimal solution. Additionally, we consider how the number of edits can be further reduced in several iterations. The running time for establishing an initial editing and for each improving iteration is linear with respect to the number of nodes plus the number of edges the graph admits. Data structures for a respective implementation get introduced as well. To make convergence in a local minimum more difficult, we propose an approach how certain decisions in the algorithm can be randomized. In experiments on various testing instances, the presented algorithm leads to better results than from previously proposed heuristics for quasi-threshold editing. Further, we confirm its scalability in practice.

Complexity of Graph Drawing Problems in Relation to the Existential Theory of the Reals

  • Datum: Fr, 18 Sep 2020, 14:00
  • Ort: SR 301
  • Vortragende(r): Nicholas Bieker, ITI Wagner; Bachelor Thesis
  • Inhalt: In dieser Arbeit beschäftigen wir uns mit der Komplexitätsklasse existsR, welche über die Existentielle Theorie der Reellen Zahlen definiert wird. Das ist eine Menge von existenziell quantifizierten wahren Formeln, die aus logischen Verknüpfungen von Polynomgleichungen und Polynomungleichungen über reellen Zahlen bestehen. Das zugehörige Entscheidungsproblem, das für eine Formel dieser Struktur entscheidet, ob sie wahr ist, heißt ETR. Die entsprechende Komplexitätsklasse besteht dann aus allen Problemen, die in einer ETR-Formel in polynomieller Länge darstellbar sind. Wir definieren zuerst ETR und die zugehörige Komplexitätsklasse ausführlich und zeigen dann existsR-Vollständigkeit für das Problem DrawingOnSegments, wo wir einen gegebenen Graphen planar auf eine Anordnung von Variablensegmenten zeichnen müssen, wobei die Kanten gewisse Hindernissegmente nicht schneiden dürfen. Dafür konstruieren wir zuerst eine ETR-Formel für das Problem und führen dann eine Reduktion von einer gleichwertigen Variante von ETR durch.

Experiments on Node Orderings for Flow-Based Graph Partitioning

  • Datum: Fr, 28 Aug 2020, 14:00
  • Ort: SR 301
  • Vortragende(r): Robert Schmoltzi, ITI Wagner; Bachelor Thesis
  • Inhalt: FlowCutter and InertialFlowCutter are two flow based partitioning algorithms. While FlowCutter calculates cuts of high quality, it is rather slow. To accelerate flow calculations, InertialFlowCutter uses geographical coordinates. These coordinates are used to generate node orderings, which determine the order in which nodes are added to the source and target sides. Due to the use of geographical information, InertialFlowCutter is limited to the calculation of cuts on road graphs. In this thesis, we want to enable InertialFlowCutter to compute cuts on graphs without node coordinates. To achieve this, we generate node orderings based on clustering algorithms and algorithms which produce node coordinates. Then, we evaluate the node orderings based on the quality of cuts InertialFlowCutter finds, using the orderings, and the running time. We compare the cuts found with the orderings specifically to FlowCutter to test whether we are able to achieve an acceleration of the flow calculations. We show that the orderings produce good cuts and nested dissection orders of decent quality. However, FlowCutter produces good cuts with higher consistency and significantly better nested dissection orders. Additionally, the accumulated running times of the creation of the orderings and cut computation with InertialFlowCutter were often longer than the running times of FlowCutter. While the creation of the oderings was slow, we were able to achieve a significant speed-up of the flow calculations, both when calculating bipartitions and nested dissection orders.

Routenplanung für Lastzüge bei beschränktem Anhängereinsatz unter Berücksichtigung von Kundenzeitfenstern, Anhängerabstellplätzen und Umladezeiten

  • Datum: Fr, 31 Jul 2020, 14:00
  • Ort: SR 301/online
  • Vortragende(r): Anastasia Slobodyanik, ITI Wagner; Bachelor Thesis
  • Inhalt: Wir untersuchen das Problem der Routenplanung für Lastzüge (LKW mit Anhänger) mit beschränktem Anhängereinsatz. Einige Kunden können mit oder ohne Anhänger angefahren werden, sofern die Kapazität des LKW das zulässt. Andere Kunden können in der Praxis teilweise nur mit LKW erreicht werden. Dafür kann es unterschiedliche Gründe geben, wie zum Beispiel ein nicht ausreichender Platz für das manövrieren. Vor der Bedienung solcher Kunden wird der Anhänger auf einem Abstellplatz abgestellt. Wir lösen das Problem der Routenplanung für eine gegebene Sequenz von Kunden und einen Lastzug exakt. Dafür entwickeln wir einen pseudopolynomiellen Algorithmus mittels dynamischer Programmierung. Service-Zeitfenster, Zeiten für An- und Abkoppeln des Anhängers sowie Zeit für das Umladen der homogenen Ware vom Anhänger auf den LKW werden berücksichtigt.

Visualizing Dynamic Clustered Data Using Area-proportional Maps

  • Datum: Fr, 3 Jul 2020, 13:00
  • Ort: SR 301/Online
  • Vortragende(r): Christian Schnorr, ITI Wagner; Master Thesis
  • Inhalt: We explore how cluster information in graphs can be visualized naturally as countries on a map in a dynamic setting where the graph changes over time. We want there to be a strong correlation between a country's size and the size of the cluster it represents, and want to be able to react to dynamic changes of the graph in a way that preserves the viewer's mental model of the map. This is a challenging problem because popular algorithms for visualizing graphs as geographic-like maps struggle with clusters being fragmented across different countries on the map, and because redrawing the map for a new, albeit similar, input graph does generally not preserve the viewer's mental map. To address these issues, we propose a framework that guarantees to keep clusters as continuous regions in the generated maps and supports dynamic inputs by allowing for small, incremental updates such as inserting or removing regions over time. We do this by working on an intermediate plane graph whose vertices correspond to clusters in the input graph, the cluster graph, and constructing the map as a contact representation of this cluster graph while accounting for the dynamic changes in both the cluster graph and its contact representation. This framework can be applied to a variety of real-world applications, allowing us to visualize clusters in the underlying data and how they change over time, thereby enabling viewers of the visualization to detect trends in the data easily.

Multilevel Hypergraph Partitioning with Vertex Weights Revisited

  • Datum: Mo, 22 Jun 2020, 11:00
  • Vortragende(r): Nikolai Maas, ITI Sanders; Bachelor Thesis
  • Inhalt: We analyze the k-way partitioning problem for hypergraphs with vertex weights and specifically the task of finding a balanced partition within the multilevel context. Problems from practical applications such as VLSI design and sparse matrix-vector multiplication naturally incorporate weighted instances, but the topic is only partially covered by current state-of-the-art partitioners. We investigate existing definitions of the balance constraint for weighted hypergraphs and propose a new generalized definition. In order to construct a partitioning algorithm that guarantees a balanced solution, we examine different aspects of the multilevel paradigm. In particular, additional measures are necessary for k-way partitioning via recursive bisection. To address this, we develop an approach based on an assignment of heavy vertices as fixed vertices to both blocks of the bisection and use theoretical results to prove that the balance of the final partition can be guaranteed. Our algorithm is integrated into the hypergraph partitioner KaHyPar and is evaluated in extensive computational experiments. Unlike the competing algorithms, our configuration always computes a balanced partition on the tested instances. The solution quality is equivalent to the current version of KaHyPar while slightly improving the running time.

Scalable Radiation Model Implementation Using Shortest-Path Distances

  • Datum: Fr, 5 Jun 2020, 14:00
  • Vortragende(r): Adrian Cierpka, ITI Wagner; Bachelor Thesis
  • Inhalt: Das Verkehrsaufkommen in einer Region zu bestimmen ist keine einfache Aufgabe. Es benötigt viele Daten und die Erfahrung von Experten um hochqualitative Verkehrsdaten zu berechnen. Somit ist die Erstellung solcher Daten teuer und zeitaufwändig. Meistens werden die Ergebnisse nicht veröffenlicht und so gibt es Bedarf für Algorithmen die ein ungefähres, realistisches Verkehrsaufkommen in einer Region berechnen. Dabei dürfen solche Algorithmen nur Daten benötigen, die öffentlich verfügbar sind und müssen einfach zu bedienen sein. Die Verkehrsdaten die man mit solchen Algorithmen berechnen kann, werden in Benchmarks verwendet um Verkehrsalgorithmen zu testen. Buchhold et al. haben in ihrer Arbeit Implementierungen des Radiation-Modells vorgestellt und mit diesen gute Ergebnisse erzielt. Zwei dieser Algorithmen heißen DRAD und TRAD. DRAD überzeugt mit guten Ergebnissen, ist aber langsamer als TRAD, welcher jedoch schlechtere Ergebnisse erzielt. In dieser Arbeit stellen wir einen Algorithmus vor, der wie TRAD eine Baum-basierte Suche verwendet. Anstatt georaphischer Distanzen nutzen wir jedoch kürzeste Pfad Distanzen. Dieser Algorithmus, CRAD genannt, liefert die gleiche Ergebinsqualität wie DRAD, ist aber in den meisten Experimenten deutlich schneller. Des Weiteren zeigen wir am Ende dieser Arbeit, dass wir nur mit Daten, die öffentlich verfügbar sind gute Ergebnisse erzielen können.

Min-cost flow algorithms for the Wind Farm Cabling Problem

  • Datum: Fr, 8 Mai 2020, 14:00
  • Vortragende(r): Marc Jenne, ITI Wagner; Bachelor Thesis
  • Inhalt: The Wind Farm Cabling Problem (WCP) describes the problem of finding a suitable cabling between a set of turbines and substations in wind farms with the goal of transmitting the whole electricity produced by the turbines to the substations. While there exist numerous possibilities of feasible cablings, it is of interest to find the one that minimizes the total costs of the required cables. This problem can be modeled as a Minimum-Cost Flow Problem (MCF), a well-known problem for which multiple algorithms already exist. These algorithms are proven to find an optimal solution in polynomial time; however, they cannot be used for the WCP without adaptions because of the primary difference between both problems: while the cost function is linear in the MCF, it is a non-linear step function in the WCP. We take a closer look at some of those algorithms and examine whether they can be adapted so that they are able to provide solutions for the WCP. We describe the algorithms and their different approaches to solve the MCF and outline the problems that arise once the cost function becomes non-linear. We present our adaption of the Successive Shortest Path Algorithm and provide multiple strategies to solve the WCP with this algorithm. In an experimental evaluation, we compare the best of these strategies to a NCC algorithm and an exact MILP solver in terms of running times and quality of the found solutions.

A Comparative Analysis of Switchings in Static and Dynamic Power Grids

  • Datum: Di, 28 Apr 2020, 13:00
  • Vortragende(r): Adrian Grupp, ITI Wagner - Master's Thesis
  • Inhalt: The power grid is the largest machine humankind has ever built. However, this machine is facing wide-ranging structural change. The transition towards intensive usage of renewable energy sources introduces new challenges: How do we cope with their volatility and how can we use them as efficiently as possible? Exploiting structural properties may be one answer to this. On one hand it is known that purposefully removing transmission lines from a power grid, so called switching, can in fact resolve congestions and overloads, which can eventually lead to a higher power throughput. In the language of graph theory this can be formalized as an optimization problem on flow networks, the Maximum Transmission Switching Flow Problem. On the other hand the concern is that the power grid can be compromised by such big topological interventions as the removal of a whole transmission line. Stable operation has to be guaranteed at all times which means adhering to the network's utility frequency. The oscillator model, used in statistical physics, can be utilized to study the transient behavior of the power grid. With it we can investigate whether switchings still allow network synchronization. Additionally, small signal analysis can be used to analyze the stability of the system after the switching took place. In this work we give a comparative analysis of the two mentioned approaches. We study how optimization results from the static world of graph theory behave in the dynamic setting of real world power grids and assess if they are reasonable with regards to the stability of the network frequency. We want to shed light on the derivation of the models and give a first answer to the question whether we can safely use switching in order to improve our power grids. Where? DFNconf Meeting Room Name: Adrian Grupp Abschlussvortrag DFNconf Meeting Room Number: 979145276 DFNconf Meeting Link: https://conf.dfn.de/webapp/conference/979145276

Wintersemester 2019

Acyclic n-Level Hypergraph Partitioning

  • Datum: Do, 19 Mär 2020, 10:00
  • Ort: -
  • Vortragende(r): Daniel Seemaier, ITI Sanders; Master Thesis
  • Inhalt: Directed acyclic graphs are widely used to model the data flow and execution dependencies of streaming applications. Efficient parallelization of such graphs requires acyclic partitioning of the dependency graph. However, normal graphs are not always capable of precisely modelling such dependencies. Thus, we consider directed acyclic hypergraphs (DAHs). In this work, we present the first n-level hypergraph partitioning algorithm for directed acyclic hypergraphs. Moreover, we show (i) that our algorithm beats the current state of the art for directed acyclic graph partitioning in terms of solution quality on realistic instances, (ii) that n-level algorithms are superior to single level algorithms, and (iii) that our algorithm improves on the makespan of a parallelized image streaming application.

PASAR – Planning as Satisfiability with Abstraction Refinement

  • Datum: Mi, 5 Feb 2020, 14:00
  • Ort: R -119
  • Vortragende(r): Nils Froleyks, ITI Sanders; Master Thesis
  • Inhalt: We present a new algorithm for the satisficing (non-optimal) classical planning problem. The presented planner participated in the Sparkle Planning Challenge 2019 and won a considerable share (22.13%) of the first prize. We combine SAT-based planning with forward state space search using the principles of counterexample-guided abstraction refinement (CEGAR). A state-of-the-art SAT solver is used to solve an abstraction of the planning task at hand. As an abstraction, we use an incomplete encoding where interference between actions is ignored. With a graph-theoretic test we determine whether the solution found by the SAT solver can be directly transformed into a plan. If it can be transformed, we realize an encoding allowing the application of many actions in parallel (exist-step semantics) in a very compact manner, without imposing a fixed order on the actions. If the transformation is not possible, we use the solution to define a heuristic function that is used during a state space search. If the search fails to find a plan within a very short timeout, the abstraction is refined. To increase the synergy between SAT solving and forward search, both can learn new actions and add them to the problem. This allows the SAT solver to make big jumps in the search space, while the forward search benefits from the SAT solver’s ability to solve combinatorially hard problems. Using benchmark domains from recent international planning competitions, we compare our approach with various state-of-the-art planners from the fields of SAT-based planning and heuristic search. On almost all tested domains we can match the performance of the best tested solvers and on some domains we outperform the entire competition.

Improving the Compact Bit-Sliced Signature Index COBS for Large Scale Genomic Data

  • Datum: Fr, 10 Jan 2020, 14:00
  • Ort: SR 301
  • Vortragende(r): Daniel Ferizovic, ITI Sanders; Master Thesis
  • Inhalt: In this thesis we investigate the potential for improving the Compact Bit-Sliced Signature Index (COBS) [BBGI19] for large scale genomic data. COBS was developed by Bingmann et al. and is an inverted text index based on bloom filters. It can be used to index k-mers of DNA samples or q-grams of plain text data and is queried using approximate pattern matching based on the k-mer (or q-gram) profile of a query. In their work Bingmann et al. demonstrated a couple of advantages COBS has over other state of the art approximate k-mer bases indices, some of which are extraordinary fast query and construction times, but as well as the fact that COBS can be constructed and queried even if the index does not fit into main memory. This is one of the reasons we decided to look more closely at some areas we could improve COBS. Our main goal is to make COBS more scalable. Scalability is a very important factor when it comes to handling DNA related data. This is because the amount of sequenced data stored in publicly available archives nearly doubles every year, making it difficult to handle even from the perspective of resources alone. We focus on two main areas in which we try to improve COBS. Those are index compression through clustering and distribution. The thesis presents our findings and improvements achieved in respect to those areas.

Weighted F-Free Edge Editing

  • Datum: Fr, 13 Dez 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Jonas Spinner, ITI Wagner; Bachelor Thesis
  • Inhalt: The Weighted F-free Edge Editing Problem asks for a set of edge edits (insertions/deletions) with minimum cost so that the edited graph does not contain induced subgraphs from a given finite set F. We focus on adapting an exact FPT algorithm for unweighted editing to the weighted case and compare it against an ILP. We evaluate the algorithms and a set of speed-up techniques on protein-protein interaction networks for F = {C4, P4}. We compare the effect of lower bound algorithms, subgraph selection rules for branching and parameter search strategies on the FPT algorithm.

Solving geometric optimization problems by reinforcement learning: crossing minimization

  • Datum: Mi, 11 Dez 2019, 13:00
  • Ort: SR 301
  • Vortragende(r): Yani Kolev, ITI Wagner; Master Thesis
  • Inhalt: Visualising relations between data points is an increasingly important problem in both everyday life and and numerous fields of scientific research. As the number of crossings is among the most important qualities of a graph drawing, over the years many approaches to minimising it have been developed. Due to the recent success of techniques based on Reinforcement Learning in the realm of game playing AI, we propose a new approach to crossing minimisation based on this technology. We base our algorithm on the Monte Carlo Tree Search, which utilises a Neural Network to guide the placement of each vertex in the graph drawing. Our framework is designed to allow easy adaptation to other similar domains. We train the network using a graph embedding tool - node2vec. Our results suggest that Monte Carlo Tree Search does indeed offer a large improvement on the crossing number over random chance, but the neural network we use to iteratively enhance it does not capitalise on the information provided by node2vec. We relive that incorporating concrete geometric data in the node2vec representation would vastly improve our results, as would alternate, more suitable embedding algorithms.

Routenplanung mit temporären Straßensperrungen und ortsabhängigen Wartekosten

  • Datum: Fr, 29 Nov 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Jakob Wagenblatt, ITI Wagner; Bachelor Thesis
  • Inhalt: In dieser Arbeit untersuchen wir das Problem der Routenplanung auf einem Straßennetzwerk mit temporären Sperrungen. In vielen Ländern ist es Lastkraftwagen-Fahrern verboten, bestimmte Straßen in einem spezifizierten Zeitraum zu befahren. Zusätzlich existieren regional beschränkte Sperrungen, wie zum Beispiel Nachtfahrverbote in Städten. Aufgrund dieser Einschränkungen können Fahrer sich gezwungen sehen, auf Parkplätzen zu warten. Wir definieren in dieser Arbeit ein Modell, welches das Finden von geeigneten Parkplätzen bereits in der Routenplanung berücksichtigt. Außerdem priorisieren wir das Warten an Parkplätzen guter Qualität, um den Reisekomfort des Fahrers zu verbessern. Weiterhin minimieren wir sowohl die Ankunftszeit als auch die Fahrzeit. Da die beiden letztgenannten Kriterien jedoch nicht immer vereinbar sind, bieten wir gegebenenfalls mehrere mögliche Routen an. Wir entwerfen einen Algorithmus, der diese Routen effizient berechnet. Anschließend analysieren wir die Eigenschaften und Komplexität des Modells wie auch des Algorithmus. Die Laufzeit des Algorithmus verbessern wir mithilfe einer Kombination aus bewährten und neuen Beschleunigungstechniken. Dies führt zu einer durchschnittlichen Laufzeit von unter einer Sekunde für europaweite Anfragen.

Cube&Conquer-inspired Techniques for Parallel Automated Planning

  • Datum: Fr, 8 Nov 2019, 14:00
  • Ort: SR 301
  • Vortragende(r): Jean-Pierre van der Heydt, ITI Sanders; Bachelor Thesis
  • Inhalt: The field of automated planning is concerned with the automatic generation of plans for different domains of problems. To allow the usage in as many fields as possible, only minimal assumptions are made to the domains. Since the complexity of these problems require a great amount of computation resources, the usage of multi core systems becomes more important. Nevertheless, there exists no clear best strategy to solve the planning problem in parallel. Cube and Conquer has proven to be a new and successful approach for solving problems of propositional logic in parallel. In this thesis we will translate the ideas of Cube and Conquer to automated planning. We focus on the realisation of cubes through nodes in the state space graph of the planning problem. In doing so, we present techniques to generate the cubes and assign computation time to them. Thereby we hope to approach parallel planning from a new angle. We are able to solve more problems than a comparable sequential algorithm. On hard test cases our algorithm scales well for up to eight cores. On easy test cases or when using more than eight cores we achieve no significant speedup.

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