Institut für Theoretische Informatik, Algorithmik
Suche
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Lehre
Sommersemester 2010
Forschungsseminar

Forschungsseminar

Sommersemester 2023

Crossing-Minimal Point-Set Embedding

  • Datum: Fr, 28 Jul 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Graph Drawing Praktikum, Abschlussvorträge
  • Inhalt: Abschlussvorträge aus dem Graph Drawing Praktikum. Drei Vorträge von jeweils 20 Minuten. Aufgabe: https://mozart.diei.unipg.it/gdcontest/2023/live/

Arc-Flags Meet Trip-Based Public Transit Routing

  • Datum: Fr, 30 Jun 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Patrick Steil, Probevortrag SEA
  • Inhalt: We present Arc-Flag TB, a journey planning algorithm for public transit networks which combines Trip-Based Public Transit Routing (TB) with the Arc-Flags speedup technique. Compared to previous attempts to apply Arc-Flags to public transit networks, which saw limited success, our approach uses stronger pruning rules to reduce the search space. Our experiments show that Arc-Flag TB achieves a speedup of up to two orders of magnitude over b, offering query times of less than a millisecond even on large countrywide networks. Compared to the state-of-the-art speedup technique Trip-Based Public Transit Routing Using Condensed Search Trees (TB-CST), our algorithm achieves similar query times but requires significantly less additional memory. Other state-of-the-art algorithms which achieve even faster query times, e.g., Public Transit Labeling, require enormous memory usage. In contrast, Arc-Flag TB offers a tradeoff between query performance and memory usage due to the fact that the number of regions in the network partition required by our algorithm is a configurable parameter. We also identify a previously undiscovered issue in the transfer precomputation of TB, which causes both TB-CST and Arc-Flag TB to answer some queries incorrectly. We provide discussion on how to resolve this issue in the future. Currently, Arc-Flag TB answers 1-6% of queries incorrectly, compared to over 20% for TB-CST on some networks.

Kurzvortrag

  • Datum: Fr, 23 Jun 2023, 14:15
  • Ort: SR 301
  • Vortragende(r): Dominik Sucker, Bachelorarbeit

The Real Polynomial Hierarchy

  • Datum: Fr, 23 Jun 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Tim Junginger, ITI Wagner, Bachelorarbeit, Kurzvortrag

Towards the Evaluation of Graph Embeddings with Deep Decoders

  • Datum: Fr, 16 Jun 2023, 14:30
  • Ort: SR 301
  • Vortragende(r): Paul Wagner
  • Inhalt: Bachelor thesis presentation

Graph Representations using Tetrahedra Contact Representations

  • Datum: Fr, 16 Jun 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Tobias Knorr, Abschlussvortrag Msc -- ITI Wagner

Dynamic Flows with Time-Dependent Capacities

  • Datum: Fr, 26 Mai 2023, 14:30
  • Ort: SR 301
  • Vortragende(r): Adrian Feilhauer
  • Inhalt: Dynamic network flows, sometimes called flows over time, extend the notion of network flows to include a transit time for each edge. While Ford and Fulkerson showed that certain dynamic flow problems can be solved via a reduction to static flows, many advanced models considering congestion and time-dependent networks result in NP-hard problems. To increase understanding of these advanced dynamic flow settings we study the structural and computational complexity of the canonical extensions that have time-dependent capacities or time-dependent transit times. If the considered time interval is finite, we show that already a single edge changing capacity or transit time once makes the dynamic flow problem weakly NP-hard. In case of infinite considered time, one change in transit time or two changes in capacity make the problem weakly NP-hard. For just one capacity change, we conjecture that the problem can be solved in polynomial time. Additionally, we show the structural property that dynamic cuts and flows can become exponentially complex in the above settings where the problem is NP-hard. We further show that, despite the duality between cuts and flows, their complexities can be exponentially far apart.

Towards a Theoretical Analysis of the Routing Architecture KIRA

  • Datum: Fr, 26 Mai 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Wendy Yi
  • Inhalt: With the increasing sizes of networks, the demand for more scalable and dynamic routing algorithms on networks grows. KIRA is a newly developed routing architecture for networks which consists of the ID-based routing protocol R^2/Kad. Experiments suggest that R^2/Kad is able to provide control plane connectivity, and to find short paths in most cases, while being highly scalable and robust. We initiate a theoretical analysis on properties of KIRA such as connectivity and the quality of the found routes.

Exploring Clique-Partitioned Treewidth

  • Datum: Fr, 12 Mai 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Sven Geißler, BA Kurzvortrag (Scale)
  • Inhalt: In a clique-partitioned tree-decomposition of a graph G, we annotate each bag X with a partition of G[X] into cliques C_i, such that the sum of log(|C_i|+1) is low. In this thesis we explore the tractability of different problems under this parameter.

Minimal Asymmetric Hypergraphs

  • Datum: Fr, 28 Apr 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Dominik Bohnert, Abschlussvortrag Bsc - ITI Wagner
  • Inhalt: An k-graph is a hypergraph where every edge has size k. If every automorphism on a k-graph G is the identity we say that G is asymmetric. Furthermore we call G minimal asymmetric, if G is asymmetric and every non trivial induced subgraph on at least two vertices of G is not asymmetric. In 2016 Schweitzer and Schweitzer confirmed a conjecture by Nesetril that there are only finitely many minimal asymmetric graphs. In this thesis we study minimal asymmetry of k-graphs. We extend a result by Jiang and Nesetril to show, that in contrast to the case k = 2, for every k at least 3 there are infinitely many asymmetric k-graphs that are linear and have maximum degree 2. We generalize the concept of the degree of asymmetry introduced to graphs by Erdoes and Renyi to the setting of k-graphs. Then we consider regular asymmetric k-graphs which have some interior symmetry as every vertex has the same degree. To conclude we survey an algorithm due to Luks that decides in simply exponential running time whether a given hypergraph is minimal asymmetric.

Efficient Embedding of Scale-Free Graphs in a Weighted Geometric Space

  • Datum: Di, 25 Apr 2023, 13:00
  • Ort: SR 236
  • Vortragende(r): Markus Wünstel

Komplexitätsanalyse des Lawn Mowing Problems und verwandter Probleme

  • Datum: Fr, 21 Apr 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Mirco Volk, Bachelorarbeit

Cable Layout Optimization Problems in the Context of Renewable Energy Sources

  • Datum: Mo, 17 Apr 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Sascha Gritzbach, Probevortrag Verteidigung

Geometric Inhomogeneous Random Graphs for Algorithm Engineering

  • Datum: Do, 6 Apr 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Chris, Probevortrag Verteidigung
  • Inhalt: The design and analysis of graph algorithms is heavily based on the worst case. In practice, however, many algorithms perform much better than the worst case would suggest. Furthermore, various problems can be tackled more efficiently if one assumes the input to be, in a sense, realistic. The field of network science, which studies the structure and emergence of real-world networks, identifies locality and heterogeneity as two frequently occurring properties. A popular model that captures these properties are geometric inhomogeneous random graphs (GIRGs), which is a generalization of hyperbolic random graphs (HRGs). Aside from their importance to network science, GIRGs can be an immensely valuable tool in algorithm engineering. Since they convincingly mimic real-world networks, guarantees about quality and performance of an algorithm on instances of the model can be transferred to real-world applications. They have model parameters to control the amount of heterogeneity and locality, which allows to evaluate those properties in isolation while keeping the rest fixed. Moreover, they can be efficiently generated which allows for experimental analysis. While realistic instances are often rare, generated instances are readily available. Furthermore, the underlying geometry of GIRGs helps to visualize the network, e.g.,~for debugging or to improve understanding of its structure. The aim of this work is to demonstrate the capabilities of geometric inhomogeneous random graphs in algorithm engineering and establish them as routine tools to replace previous models like the ErdH{o}s-R{'e}nyi model, where each edge exists with equal probability. We utilize geometric inhomogeneous random graphs to design, evaluate, and optimize efficient algorithms for realistic inputs. In detail, we provide the currently fastest sequential generator for GIRGs and HRGs and describe algorithms for maximum flow, directed spanning arborescence, cluster editing, and hitting set. For all four problems, our implementations beat the state-of-the-art on realistic inputs. On top of providing crucial benchmark instances, GIRGs allow us to obtain valuable insights. Most notably, our efficient generator allows us to experimentally show sublinear running time of our flow algorithm, investigate the solution structure of cluster editing, complement our benchmark set of arborescence instances with a density for which there are no real-world networks available, and generate networks with adjustable locality and heterogeneity to reveal the effects of these properties on our algorithms.

Wintersemester 2022

Projektantrag: Necessary and Sufficient Conditions for the Existence of a Product Structure

  • Datum: Fr, 31 Mär 2023, 15:00
  • Ort: SR 301
  • Vortragende(r): Lena Scherzer, Samuel Schneider, Praxis der Forschung

The Complexity of the Oriented Cycle Game

  • Datum: Fr, 31 Mär 2023, 14:30
  • Ort: SR 301
  • Vortragende(r): Shabi Shabani, Bsc-Abschluss ITI-Wagner
  • Inhalt: The oriented cycle game, which was introduced by Bollobás and Szabó, is a strategy game played on undirected graphs in which both players, A(voider) and C(reator), assign orientations to undirected edges alternately until there are no more undirected edges. Unlike the original game, where player C tries to create a directed cycle and player A tries to prevent him, we introduce two new variations. First, we introduce the avoid oriented cycle game, where both players try to prevent a directed cycle. The first player to create a directed cycle loses. Next, we introduce the seek oriented cycle game, where both players try to create a directed cycle. The first player to create a directed cycle wins. Following, we introduce the oriented edge groups, which is a relation between oriented edges. Here, a player, when orienting an undirected edge, must orient the other edges that are in relation to the undirected edge accordingly.

Mixed Page Number of Planar Directed Acyclic Graphs

  • Datum: Fr, 31 Mär 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Deborah Haun, Bachelorarbeit
  • Inhalt: A q-queue s-stack layout consists of a topological ordering of the vertices of a graph and a partition of its edges into q sets of edges, called queues, and s sets of edges, called stacks, such that any two edges in the same queue do not nest and any two edges in the same stack do not cross. Here, two edges nest if the endpoints of one edge are located between the endpoints of the other edge. Two edges cross if their endpoints alternate in the topological ordering. The minimum number q + s of queues and stacks required for a q-queue s-stack layout is called the mixed page number. We investigate the mixed page number of upward planar graphs and directed acyclic 2-trees. We find a subclass of upward planar bipartite graphs whose mixed page number is bounded by a constant. In addition, we give a lower bound of 3 on the mixed page number of upward planar bipartite graphs and find an upward planar bipartite graph, whose mixed page number is strictly smaller than its stack and queue number. For directed acyclic 2-trees, we show that the mixed page number is unbounded. In contrast, we present a family of directed acyclic 2-trees with bounded mixed page number but unbounded stack and queue number.

LARA: Werkzeug zur Literaturrecherche

  • Datum: Fr, 31 Mär 2023, 13:30
  • Ort: SR 301
  • Vortragende(r): Gregor Czubayko, Paul David Gauer, Johannes Breitling, Linus Buck, Thomas Roth, Abschlusspräsentation PSE

On the Connection Between Exactly Solving and Approximating Vertex Cover

  • Datum: Mi, 29 Mär 2023, 14:00
  • Ort: SR 236
  • Vortragende(r): Carina Weber, Masterarbeit ITI Bläsius
  • Inhalt: This thesis investigates the greedy algorithm for the vertex cover problem, which selects a vertex with the highest degree at each step. Despite having an upper bound of O(log n) for the cover size, this bound is much higher than most ratios on real- world graphs. The problem has been studied previously, for example on hyperbolic random graphs, but we examine the impact of tie-breaking between vertices and the probability-distribution of all greedy vertex covers, instead of individual covers, which has not been adequately investigated. To this end we introduce an enumeration algorithm for all greedy vertex covers of a graph, which can be time-consuming, and thus we propose several optimizations to improve efficiency. Our experiments reveal that the optimizations are effective in reducing the running time and can handle larger graphs than before. Additionally, we demonstrate that the upper bound of O(log n) for the cover size of the greedy algorithm is not closely approached by any graph in our set concerning the ratio between the minimum and greedy cover size. According to the data we obtained from executing the enumeration algorithm on a set of graphs, we found that the cover size for these graphs increases with a ratio between 1.0 and 1.1 with high probability.

Kurzvortrag: Necessary and Sufficient Conditions for the Existence of a Product Structure

  • Datum: Fr, 10 Mär 2023, 14:30
  • Ort: SR 301
  • Vortragende(r): Lena Scherzer, Samuel Schneider, Praxis der Forschung
  • Inhalt: The row treewidth of a graph $G$ is the minimum integer $k$ such that a path $P$ and a graph $H$ exist with $ w(H) leq k$ and $G subseteq H oxtimes P$. A family of graphs $mathcal{G}$ has product structure if and only if the row treewidth of $mathcal{G}$ is bounded. A known necessary condition for the row treewidth to be bounded is emph{linear local treewidth}. However, it is unclear whether this condition is also sufficient. We want to examine intersection graphs of homothetic $alpha$-free triangles in the plane, meaning triangles with a certain amount $alpha$ of their area disjoint from any other triangle. While it is clear that for some $alpha$ the local treewidth is not linear, we want to examine whether there exists an $alpha$ such that the local treewidth is linear, but for which product structure does not exist. This would prove, that linear local treewidth is not sufficient for the existence of product structure.

Combining Geometric Inhomogeneous Random Graphs with the Stochastic Block Model

  • Datum: Fr, 10 Mär 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Florian Küfner, BA Abschlussvortrag

Towards Homogenizing Heterogeneous Graphs with Underlying Geometry

  • Datum: Fr, 3 Feb 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Nils Schewe, Bachelor Presentation

Efficiently Computing Directed Minimum Spanning Trees (ALENEX rehearsal)

  • Datum: Fr, 20 Jan 2023, 14:15
  • Ort: SR 301
  • Vortragende(r): Chris, Master (rating: 2124)
  • Inhalt: Computing a directed minimum spanning tree, called arborescence, is a fundamental algorithmic problem, although not as common as its undirected counterpart. In 1967, Edmonds discussed an elegant solution. It was refined to run in $O(min(n^2, mlog n))$ by Tarjan which is optimal for very dense and very sparse graphs. Gabow et al.~gave a version of Edmonds' algorithm that runs in $O(nlog n + m)$, thus asymptotically beating the Tarjan variant in the regime between sparse and dense. Despite the attention the problem received theoretically, there exists, to the best of our knowledge, no empirical evaluation of either of these algorithms. In fact, the version by Gabow et al.~has never been implemented and, aside from coding competitions, all readily available Tarjan implementations run in $O(n^2)$. In this paper, we provide the first implementation of the version by Gabow et al.~as well as five variants of Tarjan's version with different underlying data structures. We evaluate these algorithms and existing solvers on a large set of real-world and random graphs.

queue and stack numbers and Boolean and DM-dimension of posets

  • Datum: Fr, 20 Jan 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Miriam Goetze, ITI Wagner -- Msc Kurzvortrag (15min)

Towards the Evaluation of Graph Embeddings with Deep Decoders

  • Datum: Mi, 18 Jan 2023, 13:00
  • Ort: SR 236
  • Vortragende(r): Paul Wagner

Komplexität des Lawn Mowing Problem

  • Datum: Fr, 13 Jan 2023, 14:00
  • Ort: SR 301
  • Vortragende(r): Mirco Volk, ITI Wagner, Bachelorarbeit, Kurzvortrag
  • Inhalt: Gegeben seien ein Polygon P und ein Rasenmäher in Form eines Einheitskreises. Wie schwierig ist es, eine kürzeste Route zu finden, die jeden Punkt des Polygons mäht.

Branching Algorithm for Power Domination Set

  • Datum: Fr, 16 Dez 2022, 14:45
  • Ort: SR 301
  • Vortragende(r): Julia Lutzweiler, MA Kurzvortrag

Theoretic Analysis of KIRA

  • Datum: Fr, 16 Dez 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Wendy Yi, MA Kurzvortrag

Classification of Gas Networks: A Graph-Theoretic Approach

  • Datum: Fr, 16 Dez 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Marc Jenne, ITI Wagner, Masterarbeit
  • Inhalt: Gas networks account for a large share of energy supply both in households and industry. They are present in all region types, such as large cities, rural areas and industrial areas. It is of interest to see whether gas networks can be classified based on the region type which they originate from. This is possible if gas networks from similar regions share important common characteristics and if gas networks from different regions differ significantly from each other. We present a graph-theoretic approach to characterise and classify gas networks originating from different region types. For this purpose, we model gas networks as graphs and examine several parameters that describe graphs from various perspectives. Using a data set of gas network instances with known origins, we analyse the common features and differences both between networks from the same region type and between networks from different types. Based on these analyses we find distinguishable gas network classes as well as meaningful parameters that characterise these classes.

Tetraeder-Kontaktdarstellungen

  • Datum: Mi, 14 Dez 2022, 13:00
  • Ort: SR 236
  • Vortragende(r): Tobias Knorr, Msc-Arbeit, Kurzvortrag (15min)

Random Minimum Spanning Trees in the Hyperbolic Plane

  • Datum: Mi, 7 Dez 2022, 13:00
  • Ort: SR 236
  • Vortragende(r): Yavor Lakov

Kurzvortrag: Mixed Page Number of Upward Planar Graphs

  • Datum: Fr, 2 Dez 2022, 14:15
  • Ort: SR 301
  • Vortragende(r): Deborah Haun
  • Inhalt: A directed graph is upward planar if it admits a planar drawing, where all edges are going upwards. A q-queue s-stack layout consists of a topological ordering of the vertices of a graph and a partition of its edges into q sets of edges, called queues, and s sets of edges, called stacks, such that any two edges in the same queue do not nest and any two edges in the same stack do not cross. Here, two edges nest if the endpoints of one edge are located between the endpoints of the other edge, and two edges cross if their endpoints alternate in the topological ordering. The minimum number s + q of queues and stacks needed for a q-queue s-stack layout is called the mixed page number. First, we determine the mixed page number of some concrete graphs. Then we investigate the mixed page number for the class of upward planar bipartite graphs before we try to find upper and lower bounds to the mixed page number of all upward planar graphs.

Kurzvortrag: Oriented Cycle Game

  • Datum: Fr, 2 Dez 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Shabi Shabani

Variable Neighborhood Search for the Solar Farm Cable Layout Problem

  • Datum: Fr, 25 Nov 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Leonie Wahl
  • Inhalt: Das Verkablungsproblem in Solarparks ist das Optimierungsproblem, für einen gegebenen Solarpark die kostengünstigste Verkablung zu finden, die zugleich verschiedene Bedingungen, wie das Einhalten von Kapazitäten der Komponenten, erfüllt. In früheren Arbeiten wurde bereits eine MILP Formulierung und eine heuristische Methode für dessen Lösung entworfen. Wir stellen eine Anwendung der Metaheuristik Variable Neighborhood Search (VNS) für das Verkablungsproblem in Solarfarmen vor. Die Performance dieser Metaheuristik wird getestet und verglichen mit der existierenden MILP Formulierung und Heuristik.
  • Datum: Fr, 11 Nov 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Nicholas Bieker, ITI Bläsius, ITI Wagner, Masterarbeit
  • Inhalt: There are many problems of geometric nature that are complete in the complexity class ER. We examine what happens to the complexity of these problems when considering hyperbolic geometry. For that, we start with line arrangements and the SimpleStretchability problem, where we are given a pseudoline arrangement and have to decide if there is a homeomorphic line arrangement. We define the hyperbolic problem version, where the line arrangements consist of hyperbolic lines, and show that the hyperbolic and Euclidean versions are equivalent. Additionally, we consider hyperbolic unit disk graphs and show that their recognition problem is ER-complete.

Integrating Ridesharing and Public Transit Routing

  • Datum: Fr, 11 Nov 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Louis Tiede

Coloring Hypergraphs Induced by Hanging Rectangles

  • Datum: Fr, 4 Nov 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Maria Nübling, ITI Wagner, Masterarbeit
  • Inhalt: tba

Theoretical Analysis of Different Dynamic Flow Variations

  • Datum: Fr, 28 Okt 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Jannik Westenfelder, ITI Bläsius, Bachelorthesis
  • Inhalt: The dynamic max flow problem is based on the static max flow problem. It extends the base problem by adding a temporal component through a travel time for arcs. We provide an overview of the hardness of different variations of this max dynamic flow problem and the needed proofs. The dynamic max flow problem is weakly NP-hard if we allow the travel times or the capacities to change at integral points in time. These results show that, in contrast to dynamic max flow problems with arcs that have a constant travel time or capacity, allowing these changes causes the problem to become NP-hard.

Forest Stack Layouts

  • Datum: Fr, 28 Okt 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Lena Scherzer, ITI Wagner, Bachelorarbeit
  • Inhalt: A stack layout of a graph consists of an ordering of the vertices s and a partition of the edges into stacks. Two edges on the same stack are not allowed to cross with respect to s, meaning that for no two edges xy and uv with s(x) < s(y) and s(u) < s(v) in the same stack we have s(x) < s(u) < s(y) < s(v) or s(u) < s(x) < s(v) < s(y). In a forest stack layout the subgraph on each stack is a forest. The minimum number of stacks needed for a stack layout of a graph is called the stack number and the minimum number of stacks needed for a forest stack layout is called the forest stack number. We determine the forest stack number of some graphs and attack the conjecture that the forest stack number of graphs might be at most one greater than the stack number for every graph. For complete graphs, complete bipartite graphs K_{m,n} with m << n, planar 3-trees and k-trees the forest stack number or the best known bound on the forest stack number is shown to be the same as the stack number. For outerplanar graphs, one more stack is needed for forest stack layouts. We also show that for every k there is a graph with stack number k that needs k + 1 stacks for a forest stack layout. Assuming some restrictions apply, we find counterexamples to the conjecture.

Shallow Edge Sets in Hypergraphs

  • Datum: Fr, 21 Okt 2022, 14:30
  • Ort: SR 131
  • Vortragende(r): Tim Planken, ITI Wagner, Masterarbeit
  • Inhalt: Let H=(V,E) be a hypergraph. A subset M of E is t-shallow if every vertex v in V has at most t incident edges that are in M. A subset M of E is hitting if every vertex v has an incident edge in M. We consider both shallow edge sets and shallow hitting edge sets. First, we give an equivalence for the existence of shallow hitting edge sets in graphs (i.e. each edge is a 2-subset of V). Moreover, we give a sufficient condition on the minimum vertex degree for the existence of t-shallow hitting edge sets in m-uniform (m-partite) hypergraphs and prove that this condition is almost tight. Then, we provide upper and lower bounds for the smallest t=t(m) such that every m-uniform regular hypergraph has a t-shallow hitting edge set. The proof of the upper bound is constructive and uses the Lovász Local Lemma. Moreover, we consider maximum size shallow edge sets and provide a lower bound for uniform regular hypergraphs and show that this lower bound is tight up to a constant factor. We also provide an explicit construction of m-uniform m-partite regular hypergraphs through projective spaces. This construction improves the lower bound on t(m) and provides an explicit construction of an m-uniform m-partite regular hypergraph with small maximum shallow edge set. Then, we show that deciding whether an m-uniform m-partite regular hypergraph has a t-shallow hitting edge set is NP-complete. Moreover, we use the existence of shallow hitting edge sets in uniform regular hypergraphs to show an upper bound for the polychromatic coloring of the union of strips.

Primal-Dual Cops and Robbers

  • Datum: Fr, 21 Okt 2022, 14:00
  • Ort: SR 131
  • Vortragende(r): Minh Tuan Ha, ITI Wagner, Bachelorarbeit
  • Inhalt: The game of cops and robbers is a pursuit and evasion game played on graphs in which both parties alternate in taking turns to move along the edges. While the cops try to catch the robber in a finite number of moves, the robber tries to evade the cops indefinitely. Contrary to the original game in which both parties move from vertex to vertex, we introduce a new variation for planar graphs with cops that advance on faces instead. In this variation, the cop number, denoted as c^*(G), specifies how many cops are required to catch the robber, that is, by occupying all faces incident to the robber's position, even if the latter plays perfectly. We first establish general lower and upper bounds on c^*(G) for planar graphs G. From there on, we consider classes of graphs such as k-regular graphs and graphs with maximum degree Delta(G) geq 5. Here we proceed by using already proven results of the original game and applying them to our setting. Furthermore, we consider the effect of subdividing edges of graphs on the cop number c^*(G). For this, we use K_4 as an example.

Solving Power Dominating Set

  • Datum: Fr, 7 Okt 2022, 15:00
  • Ort: SR 131
  • Vortragende(r): Max Göttlicher

GIRG + Stochastic Block Model

  • Datum: Fr, 7 Okt 2022, 14:00
  • Ort: SR 131
  • Vortragende(r): Florian Küfner, BA-Kurzvortrag

Sommersemester 2022

Minimizing Planar Edge Length Ratio on the Grid

  • Datum: Fr, 30 Sep 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Luca Buchholz, ITI Wagner, Bachelorarbeit
  • Inhalt: The edge length ratio of a graph drawing is defined as the ratio obtained by dividing the length of the longest edge and the shortest Euclidean distance between any two adjacent vertices. Optimizing this ratio for planar graphs drawn on a grid is the topic of the live challenge at the 30th International Symposium on Graph Drawing and Network Visualization and this thesis. The algorithm implemented takes a given initial drawing, calculated by any known algorithm drawing planar graphs on the grid, and performs a local search starting at this drawing to optimize edge length ratio.

Packing Lower Bounds for Cluster Editing

  • Datum: Fr, 30 Sep 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Maximilian Walz, ITI Bläsius, Bachelorthesis

Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs

  • Datum: Fr, 2 Sep 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Miriam Goetze, Probevortrag, ESA 2022
  • Inhalt: It follows from the work of Tait and the Four-Color-Theorem that a planar cubic graph is 3-edge-colorable if and only if it contains no bridge. We consider the question of which planar graphs are subgraphs of planar cubic bridgeless graphs, and hence 3-edge-colorable. We provide an efficient recognition algorithm that given an n-vertex planar graph, augments this graph in O(n^2) steps to a planar cubic bridgeless supergraph, or decides that no such augmentation is possible. The main tools involve the Generalized-Antifactor-problem for the fixed embedding case, and SPQR-trees for the variable embedding case.
  • Datum: Fr, 26 Aug 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Nicholas Bieker, ITI Bläsius, ITI Wagner
  • Inhalt: Kurzvortrag zur Masterarbeit.

Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time

  • Datum: Fr, 26 Aug 2022, 14:00
  • Ort: SR 301 and https://kit-lecture.zoom.us/j/63982875014?pwd=MVVVK1N1MDdpUFgzKzBnTU96L0Rmdz09
  • Vortragende(r): Chris, IPEC22 rehearsal
  • Inhalt: Given an undirected graph, the task in CLUSTER EDITING is to insert and delete a minimum number of edges to obtain a cluster graph, that is, a disjoint union of cliques. In the weighted variant each vertex pair comes with a weight and the edge modifications have to be of minimum overall weight. In this work, we provide the first polynomial-time algorithm to apply the following data reduction rule of Böcker et al. [Algorithmica, 2011] for WEIGHTED CLUSTER EDITING: For a graph~$G = (V,E)$, merge a vertex set~$S subseteq V$ into a single vertex if the minimum cut of~$G[S]$ is at least the combined cost of inserting all missing edges within~$G[S]$ plus the cost of cutting all edges from~$S$ to the rest of the graph. Complementing our theoretical findings, we experimentally demonstrate the effectiveness of the data reduction rule, shrinking real-world test instances from the PACE Challenge 2021 by around 24,\% while previous heuristic implementations of the data reduction rule only achieve 8,\%.

Oh the Connection Between Exactly Solving and Approximating Vertex Cover

  • Datum: Fr, 19 Aug 2022, 14:45
  • Ort: SR 301
  • Vortragende(r): Carina Weber

Homogenizing Heterogeneous Graphs with Underlying Geometry

  • Datum: Fr, 19 Aug 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Nils Schewe

Algorithm Comparison for Autonomous Mobile Robots Scheduling

  • Datum: Fr, 19 Aug 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Jakob Wagenblatt, ITI Bläsius & FZI, Masterthesis
  • Inhalt: With the advent of Industry 4.0 and increasing automation, the importance of autonomous mobile robots (AMR) for transporting goods in intralogistics is growing. Consequently, this has given rise to the development of new centralized and decentralized methods for scheduling and routing these robots. However, there is a lack of comparison between the different algorithms, which moreover often do not model important features of the real world. Therefore, we develop a discrete-event simulation framework allowing easy comparison of different scheduling algorithms for the Electric Multi-Agent Pickup and Delivery (EMAPD) problem by finding a general basis for modeling instances. The EMAPD is an online problem in which delivery tasks arrive continuously and have to be assigned to AMRs. Its solutions consists of collision-free routes that fulfill these tasks while considering battery constraints, charging as necessary and minimizing tardiness. We evaluate the performance of seven different schedulers experimentally on ten different scenarios varying in layout, size, number of robots and system load. Our experiments show that the performance of the schedulers varies wildly, depending on the scenario and especially the system load. We attribute this in part to the charging strategy used as a simple rule-based scheduler implemented for reference with a different charging strategy sometimes performs best. Overall, we rate an auction-based scheduler punishing tardiness best. On average, it produces good results and performs efficiently.

Homogenizing Heterogeneous Graphs with Underlying Geometry

  • Datum: Fr, 12 Aug 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Nils Schewe

Efficient Long-Haul Truck Driver Routing

  • Datum: Fr, 12 Aug 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Max Oesterle, ITI Wagner, Masterarbeit
  • Inhalt: Truck drivers on long-haul journeys must take breaks and rest periods due to regulatory constraints. Most regulations require the driver to take breaks of a certain minimum duration after having accumulated a maximum allowed driving time. At the same time, a break or rest period must be scheduled at a parking location which is suitable for a truck. This leads to the challenge of choosing parking locations which minimize the increase in travel time caused by the detour to the parking location, and finding the best route between start, parking locations, and the destination. The travel time is the sum of the pure driving time and the accumulated break time on the route. We call this problem the Long-Haul Truck Driver Routing Problem. We use a simplified model to abstract from real-world regulations. The problem of finding routes with the shortest travel time that comply with our model of regulations is called the Truck Driver Routing Problem (TDRP). We present a label-based algorithm which is able to solve the TDRP. The algorithm is further improved using a goal-directed search, a bidirectional search, a core contraction hierarchy, or combinations of these. The goal-directed core CH algorithm achieves average running times on a European road network of about 10 ms which allows the application of our work in practical applications.

Kurzvortrag: Coloring Hypergraphs Induced by Hanging Rectangles

  • Datum: Fr, 29 Jul 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Maria Nübling
  • Inhalt: Kurzvortrag zu Masterarbeit

Entwicklung eines Exakten Algorithmus für das Directed Feedback Vertex Set Problem

  • Datum: Fr, 29 Jul 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Ruben Götz, ITI Bläsius, Bachelorthesis
  • Inhalt: In dieser Arbeit wurde ein Algorithmus zum Lösen des Directed Feedback Vertex Set Problems entwickelt. Der Algorithmus folgt einem Branch&Bound Ansatz. Den Hauptbestandteil dieser Arbeit bildet die Reduktion von Probleminstanzen. Hierfür werden 10 Reduktionsregeln vorgestellt. Auch die Implementierung des Algorithmus wird in dieser Arbeit diskutiert. Der hier behandelte Algorithmus wurde in der Programmiersprache C++ implementiert und steht öffentlich zur Verfügung. Die Testergebnisse der Implementierung wurden in dieser Arbeit zusammengefasst.

A Branch-And-Bound Algorithm for Cluster Editing (SEA22 Testrun)

  • Datum: Fr, 22 Jul 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Chris
  • Inhalt: Read the paper if you are interested. https://doi.org/10.4230/LIPIcs.SEA.2022.13 Zoom Link: https://kit-lecture.zoom.us/j/63982875014?pwd=MVVVK1N1MDdpUFgzKzBnTU96L0Rmdz09

Kurzvortrag: Random Minimum Spanning Trees in the Hyperbolic Plane

  • Datum: Fr, 15 Jul 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Yavor Lakov

About the Analysis of Algorithms on Networks with Underlying Hyperbolic Geometry

  • Datum: Fr, 15 Jul 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Maximilian Katzmann
  • Inhalt: Many complex systems that we encounter in the world can be formalized using networks. Consequently, they have been in the focus of computer science for decades, where algorithms are developed to understand and utilize these systems. Surprisingly, our theoretical understanding of these algorithms and their behavior in practice often diverge significantly. In fact, they tend to perform much better on real-world networks than one would expect when considering the theoretical worst-case bounds. One way of capturing this discrepancy is the average-case analysis, where the idea is to acknowledge the differences between practical and worst-case instances by focusing on networks whose properties match those of real graphs. Recent observations indicate that good representations of real-world networks are obtained by assuming that a network has an underlying hyperbolic geometry. In this talk I give an overview of the findings in my thesis, where it was demonstrated that the connection between networks and hyperbolic space can be utilized as a powerful tool for average-case analysis. To this end, I will give an introduction to networks with underlying hyperbolic geometry and go through an example where the model guided us towards an algorithm that solves a hard problem more efficiently in practice.

On the External Validity of Average-Case Analyses of Graph Algorithms

  • Datum: Fr, 8 Jul 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Thomas Bläsius
  • Inhalt: also via zoom: https://kit-lecture.zoom.us/j/65303658822?pwd=UGdSbmdoRUQydktad0NwL09GTVhpdz09 The number one criticism of average-case analysis is that we do not actually know the probability distribution of real-world inputs. Thus, analyzing an algorithm on some random model has no implications for practical performance. At its core, this criticism doubts the existence of external validity, i.e., it assumes that algorithmic behavior on the somewhat simple and clean models does not translate beyond the models to practical performance real-world input. With this paper, we provide a first step towards studying the question of external validity systematically. To this end, we evaluate the performance of six graph algorithms on a collection of 2751 sparse real-world networks depending on two properties; the heterogeneity (variance in the degree distribution) and locality (tendency of edges to connect vertices that are already close). We compare this with the performance on generated networks with varying locality and heterogeneity. We find that the performance in the idealized setting of network models translates surprisingly well to real-world networks. Moreover, heterogeneity and locality appear to be the core properties impacting the performance of many graph algorithms.

Point-of-Interest Queries in Public Transit Networks

  • Datum: Fr, 1 Jul 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): John Gelhausen, Masterarbeit
  • Inhalt: We study the problem of finding the k-nearest POIs in pure public transit and multi-modal networks. For the multi-modal networks, we combine a public transit network with a non-schedule-based mode of transport. Given a departure time and a single source vertex, we want to find the k closest vertices in a set of targets, optimizing the arrival time. Our solution for pure public transit networks is a combination of two state-of-the-art algorithms: ACSA, which enables efficient one-to-one queries, and CRP, which enables efficient one-to-many queries in road networks. Our solution for multi-modal networks, k-UP-CSA, is a combination of ACSA and ULTRA-PHAST, which enables efficient one-to-many queries in multi-modal networks. We examine the performance of both our extension to ACSA and k-UP-CSA on the networks of London, Switzerland and Germany. Both algorithms achieve high speed-ups on country-sized public transit networks, such as Switzerland and Germany. On urban-sized public transit networks, our algorithms are still faster than the baseline algorithms, however the speed-up we achieve is less impressive compared to country-sized public transit networks.

Deterministic Performance Guarantees for Bidirectional BFS on Real-World Networks

  • Datum: Fr, 24 Jun 2022, 14:15
  • Ort: SR 301
  • Vortragende(r): Marcus
  • Inhalt: A common technique to speed up shortest path queries in graphs is to use a bidirectional search, i.e., performing a forward search from the start and a backwards search from the destination until a common vertex on a shortest path is found. In practice, this has a tremendous impact on the performance on some real-world networks, while it only seems to save a constant factor on other types of networks. Even though finding shortest paths is a ubiquitous problem, there are only few studies attempting to understand the apparently asymptotic speedups on some networks, using average case analysis on certain models for real-world networks. In this paper we give a new perspective on this, by analyzing deterministic properties that permit theoretical analysis and that can easily be checked on any particular instance. We prove that these parameters imply sublinear running time for the bidirectional BFS in several regimes, some of which are tight. Moreover, we perform experiments on a large set of real-world networks showing that our parameters capture the concept of practical running time well.

Variable Neighborhood Search for the Solar Farm Cable Layout Problem

  • Datum: Fr, 24 Jun 2022, 14:00
  • Ort: 315
  • Vortragende(r): Leonie Wahl
  • Inhalt: Leonie is giving a short presentation on her Bachelor's thesis.

Variable Neighborhood Search for the Solar Farm Cable Layout Problem

  • Datum: Di, 21 Jun 2022, 10:30
  • Ort: tba
  • Vortragende(r): Leonie Wahl
  • Inhalt: Short presentation on Leonie's Bachelor's thesis

Kurzvortrag: Forest Stack Layouts

  • Datum: Di, 21 Jun 2022, 10:15
  • Ort: tba
  • Vortragende(r): Lena Scherzer, ITI Wagner, Bachelorarbeit

Shallow Hitting Sets

  • Datum: Di, 21 Jun 2022, 10:00
  • Ort: 315
  • Vortragende(r): Tim Planken

Anzahl inklusionsmaximaler Cliquen in geometrischen Zufallsgraphen

  • Datum: Fr, 3 Jun 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Niko Lemke, ITI Bläsius, BA Abschlussvortrag
  • Inhalt: Krankheitsbedingt erneut verschoben (auf den 3.6.)

Kurzvortrag: Packing Lower Bounds for Cluster Editing

  • Datum: Fr, 20 Mai 2022, 14:15
  • Ort: SR 301
  • Vortragende(r): Maximilian Walz, ITI Bläsius, Bachelorthesis

Kurzvortrag: Theoretical Analysis of Different Dynamic Flow Variations

  • Datum: Fr, 20 Mai 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Jannik Westenfelder, ITI Bläsius, Bachelorthesis

Interval Colorings on Graphs

  • Datum: Fr, 6 Mai 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Michael Zheng, ITI Wagner; Bachelor Thesis
  • Inhalt: A graph G is called interval colorable if there is an assignment of integers to its edges such that each vertex is incident to edges colored by a set of consecutive integers and there are no two adjacent edges of the same color. This notion was motivated by the problem of finding compact school timetables, i.e. timetables such that the lectures of each teacher and each class are scheduled in consecutive periods. First, we survey some results in the study of interval colorability and related topics. In particular, we focus our attention on current results on the interval thickness, a relaxation of interval colorability where we want to edge-decompose the graph into as few interval colorable subgraphs as possible. After that, we will present a new upper bound on the interval thickness using a powerful tool in extremal graph theory and then show that the spectrum, which we define as the set of all positive integers t such that there is an interval coloring using the integers 1 to t, can have arbitrarily many and arbitrarily large gaps.

Minimum Linear Arrangement revisited

  • Datum: Fr, 22 Apr 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Michael Zündorf, MA Vortrag

Extending, Recombining and Evaluating Contraction Hierarchy-based Many-to-Many Shortest Path Algorithms

  • Datum: Di, 12 Apr 2022, 13:00
  • Ort: SR 301
  • Vortragende(r): Theo Wieland, ITI Wagner; Bachelor Thesis
  • Inhalt: TBA

ULTRA on Public Transit Networks with Limited Transfers

  • Datum: Fr, 8 Apr 2022, 14:30
  • Ort: SR 301
  • Vortragende(r): Alexander Vogel, ITI Wagner; Bachelor Thesis
  • Inhalt: TBA

Public Transit Routing with Real-Time Updates

  • Datum: Fr, 8 Apr 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Daniel Zhang, ITI Wagner; Bachelor Thesis
  • Inhalt: TBA

The Planar Graph Grabbing Game

  • Datum: Di, 5 Apr 2022, 13:30
  • Ort: SR 301
  • Vortragende(r): Benedikt Hahn, ITI Wagner; Bachelor Thesis
  • Inhalt: In this work we introduce a new game on graphs called “The planar graph grabbing game”. The game is played on a plane graph with vertices weighted 0 and 1. Vertices with weight 1 are called cherries. Two players – Alice and Bob starting with Alice – take turns removing single vertices (and in doing so their incident edges) from the outer face of the remaining graph. The game ends when no vertices are left and the player who obtained the most weight wins. We call an instance Bob-dominant when Bob is able to obtain all cherries on the instance, no matter which strategy Alice follows. First, we show that there are Bob-dominant instances with arbitrarily many cherries. We also prove that there are even 4-connected triangulated Bob-dominant instances with arbitrarily many cherries. We then give examples for 4-connected triangulated Bob-dominant instances of odd size with up to six cherries and prove that no such graphs can exist for seven or more cherries. Finally, we briefly pursue the question what share of cherries Alice is guaranteed to get on odd 4-connected triangulated instances with “many” cherries.

Cooperative Route Planning on Time-Dependent Road Networks

  • Datum: Di, 5 Apr 2022, 13:00
  • Ort: SR 301
  • Vortragende(r): Nils Werner, ITI Wagner; Master Thesis
  • Inhalt: TBA

On Hyperbolic Unit Disk Graphs

  • Datum: Fr, 1 Apr 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Emil Dohse, ITI Wagner; Master Thesis
  • Inhalt: Wird auch bei Zoom übertragen: https://kit-lecture.zoom.us/j/65303658822?pwd=UGdSbmdoRUQydktad0NwL09GTVhpdz09

Wintersemester 2021

Surrounding Cops and Robbers

  • Datum: Fr, 11 Mär 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Samuel Schneider, ITI Wagner; Bachelor Thesis
  • Inhalt: TBA

Minimum-Width Triangulations of Upward Planar Graphs

  • Datum: Di, 8 Mär 2022, 13:30
  • Ort: SR 301
  • Vortragende(r): Liran Dattner, ITI Wagner; Bachelor Thesis
  • Inhalt: A path cover of a graph G is a set of paths in G such that their union contains all vertices of G. The width w(G) of G denotes the size of a minimum path cover. A directed graph is called upward planar if it can be embedded such that each edge is a monotonic upwards curve and no two edges cross. In some cases, it is possible to add edges to such a graph to construct an upward planar graph with lower width. We introduce a new parameter, the triangulated width w_t(G), to describe this situation. This parameter w_t(G) is the minimum of the width of all upward planar graphs that can be obtained by adding edges to G. In particular, there always exists an upward planar triangulation of G that has a width equal to w_t(G). We establish first bounds on w_t(G) and provide exact results for some classes of graphs such as trees and series-parallel graphs. Furthermore, we discuss some algorithmic approaches for determining w_t(G) and w(G) and briefly talk about the complexity of this task.

Partitioning Geometric Graphs into Plane Subgraphs

  • Datum: Di, 8 Mär 2022, 13:00
  • Ort: SR 301
  • Vortragende(r): Jonathan Dransfeld, ITI Wagner; Bachelor Thesis
  • Inhalt: A geometric graph is a set of points in the 2D plane and a set of connecting straight-line segments, and is called plane if no two segments intersect. The problem of partitioning a geometric graph into plane subgraphs was presented in the CG:SHOP 2022 competition. In this presentation, we introduce the equivalence of this problem to the coloring problem on the intersection graph and show that this problem is NP-complete. Then, we present new heuristics for solving this coloring problem and compare it to well-known coloring heuristics like DSATUR.

Theory and Algorithms of the Solar Farm Cable Layout Problem

  • Datum: Fr, 18 Feb 2022, 14:00
  • Ort: https://kit-lecture.zoom.us/j/66091413121?pwd=SmFEcVJlYlRWcDB3aGN6WGlSbGNKQT09
  • Vortragende(r): Dominik Stampa, ITI Wagner; Master Thesis
  • Inhalt: Solar energy is a renewable and sustainable energy, which gets more and more important in times where humanity aims to reduce the usage of fossil fuels. Photovoltaic modules are used to convert sun light into electricity. Often this is done in large solar farms. We model a solar farm as layered graph, where the power generated by the strings (several connected photovoltaic modules) needs to be conducted through the layers of the graph. For the connection of two vertices there are different types of cables with different capacities and costs. The problem is now to find a cable layout with minimal costs, which does not violate cable or vertex capacities. This optimization problem is analyzed and it is shown that the Solar Farm Cable Layout Problem is NP-hard for several variants. For the general variant it is even NP hard to find any feasible solution. A heuristic algorithm to solve a special but realistic variant of the problem is proposed. It is compared and evaluated with an MILP formulation of the problem. For large solar farms the heuristic is able to find a solution to the problem where the MILP is not able to find one within 24 hours runtime.

BA Antrittsvortrag

  • Datum: Fr, 11 Feb 2022, 14:00
  • Ort: SR 301 / Zoom
  • Vortragende(r): Ruben Götz
  • Inhalt: Der Vortrag stellt das Thema einer Bachelorarbeit vor. In dieser soll ein exakter Algorithmus zum lösen des "Directed Feedback Vertex Set" Problems erstellt und bei der PACE-Challenge eingereicht werden. Ein "Directed Feedback Vertex Set" ist eine Knotenmenge in einem Graphen, die, wenn sie gelöscht wird, einen azyklischen Graphen zurück lässt. Link: https://kit-lecture.zoom.us/j/63982875014?pwd=MVVVK1N1MDdpUFgzKzBnTU96L0Rmdz09

On Difference Labellings for Directed Graphs

  • Datum: Fr, 4 Feb 2022, 14:00
  • Ort: SR 301
  • Vortragende(r): Matthew Akram, ITI Bläsius, Bachelorthesis
  • Inhalt: A directed graph G = (V, E) is a difference-digraph if there exists a labelling lambda:V->Z such that the arc (v,w) is in E if and only if there exists a z in V with lambda(v) - lambda(w) = lambda(z). An undirected graph G = (V, E) is an (integral) sum-graph if there exists a labelling lambda: V->Z such that the edge {v,w} is in E if and only if there exists a z in V with lambda(v) + lambda(w) = lambda(z). In this thesis, we investigate some combinatoric as well as some informatical properties of difference-digraphs. We present a complete dichotomy of which rooted forests are difference-digraphs, as well as present some interesting properties that aid in the classification of other graph classes. For some graph classes, we look into the minimum number of vertices one needs to add, in order to obtain a difference-digraph with the original graph as an induced sub-graph. We also investigate the decision problem of deciding if a graph is a difference-digraph, and prove that it is in NP. Lastly, we consider the efficiency of storing directed graphs as (induced sub-graphs of) difference-digraphs. We then extend our findings, and apply them to the storage of undirected graphs as induced sub-graphs of sum-graphs, by adding isolated vertices. For online attendance: Join Zoom Meeting Matthew's Bachelorthesis: On Difference Labellings for Directed Graphs https://kit-lecture.zoom.us/j/67790105592?pwd=YXVYZCt0ZGc3VVpyYzNmNTRsKzdXdz09 Time: Feb 4, 2022 01:45 PM Amsterdam, Berlin, Rome, Stockholm, Vienna Meeting ID: 677 9010 5592 Passcode: 826861

Die Anzahl maximaler Cliquen in geometrischen Zufallsgraphen

  • Datum: Fr, 17 Dez 2021, 14:30
  • Ort: SR 301 / https://kit-lecture.zoom.us/j/63982875014?pwd=MVVVK1N1MDdpUFgzKzBnTU96L0Rmdz09
  • Vortragende(r): Niko Lemke, ITI Bläsius, Intro-Talk Bachelorarbeit
  • Inhalt: In Nikos Kurzvortrag für seine Bachelorarbeit geht es darum abzuschätzen, wie viele Inklusionsmaximale Cliquen unterschiedliche Varianten von geometrischen Zufallsgraphen haben. Der Zoomlink gilt auch für Chris Vortrag um 14:00.

An Efficient Branch-and-Bound Solver for Hitting Set (ALENEX rehearsal)

  • Datum: Fr, 17 Dez 2021, 14:00
  • Ort: SR 301
  • Vortragende(r): Chris, I am great
  • Inhalt: The hitting set problem asks for a collection of sets over a universe $U$ to find a minimum subset of $U$ that intersects each of the given sets. It is NP-hard and equivalent to the problem set cover. We give a branch-and-bound algorithm to solve hitting set. Though it requires exponential time in the worst case, it can solve many practical instances from different domains in reasonable time. Our algorithm outperforms a modern ILP solver, the state-of-the-art for hitting set, by at least an order of magnitude on most instances.

On Minus labellings, A directed variant of sum labellings

  • Datum: Fr, 3 Dez 2021, 14:00
  • Ort: SR 301
  • Vortragende(r): Matthew Akram, ITI Bläsius, Intro-Talk Bachelorthesis
  • Inhalt: A graph G=(V,E) is a sum graph if there is a labelling lambda:V->mathbb{Z} such that there is an edge between vertices u and v if and only if there is a vertex with the label lambda(u)+lambda(v). In this bachelor thesis we investigate directed variants of such labelling schemes. We call a graph a minus graph if there is a labelling as above such that there is an edge from u to v if and only if there is a vertex with label lambda(u)­-lambda(v). In this talk we give an overview of our preliminary results, including some basic properties, a classification of rooted-trees and more.

Solving Dynamic Macroeconomic Models with an Entrepreneurial Sector

  • Datum: Fr, 26 Nov 2021, 14:00
  • Ort: SR 301 (tentatively)
  • Vortragende(r): Henriette Kissling, ITI Bläsius + Chair of Macroeconomics; Abschlussvortrag Bachelorarbeit
  • Inhalt: In this thesis, we make two contributions: first, we transfer an overlapping-generations model of intertemporal savings and investment decisions used to evaluate taxation systems to an equivalent infinite-horizon Aiyagari-style model. We compare the results of the two model types and investigate the mechanisms at play. Our work is the first step of an ongoing research program with the overall objective of evaluating wealth taxation in the context of heterogeneous returns. We show that the results generated by the transferred model are fairly close to the empirical data on the U.S. earnings, income and wealth distribution. Crucially, the model yields almost the same extent of inequality in terms of Gini coefficients. Second, we explore the technical boundaries of solving complex dynamic macroeco- nomic models with common methods and extend these methods in order to obtain a good compromise between accuracy and computational feasibility. We show that our approach manages to speedup the calculation by factor 9 and allows us to impose configurable standards on the minimum precision.

Asynchronous n-Level Hypergraph Partitioning

  • Datum: Mi, 24 Nov 2021, 14:00
  • Ort: https://i10meeting.iti.kit.edu/AbschlussvortragLaupichler
  • Vortragende(r): Moritz Laupichler, ITI Sanders und Wagner; Master Thesis
  • Inhalt: In this thesis, we introduce a novel approach to scalable high-quality parallel hypergraph partitioning. The balanced k-way hypergraph partitioning problem consists of partitioning the vertices of a hypergraph into k blocks of almost equal size s.t. an objective function is optimized (usually the sum of the number of blocks that each hyperedge spans should be minimized). In the n-level variant of the popular multilevel scheme, almost n contractions are performed on the hypergraph before finding an initial partitioning and then reverting the contractions. In the uncoarsening phase, after every uncontraction, localized refinement is applied around the region of the uncontraction, which leads to partitions of very high quality. In this work, we present asynchronous uncoarsening, a highly scalable parallelization of the n-level uncoarsening phase in which uncontractions and localized refinement happen concurrently. We introduce a framework that requires no global synchronization during the uncoarsening phase and allows fine-grained control of cross-dependencies between concurrent uncontractions and refinement. We implement asynchronous uncoarsening in the Mt-KaHyPar framework and experimentally compare our approach with the previous batch synchronous uncoarsening phase. Our extensive experiments on more than 500 real-world hypergraphs with up to 190 million vertices and 2 billion pins (sum of hyperedge sizes) show that our approach scales better on large hypergraphs with only a small loss of quality. We find that Mt-KaHyPar with asynchronous uncoarsening is on average 26% faster than Mt-KaHyPar with batch uncoarsening for large instances using 64 threads. Our uncoarsening phase reaches average self-relative speedups of 39 for 64 threads on difficult instances for which the average speedups of Mt-KaHyPar's batch uncoarsening are limited to less than 24.

Maximal k-Degenerate Spanning Subgraphs

  • Datum: Fr, 19 Nov 2021, 14:00
  • Ort: SR 301
  • Vortragende(r): Nadine Krisam, ITI Wagner; Master Thesis
  • Inhalt: In this thesis we discuss maximum k-degenerate spanning subgraphs. A spanning subgraph is a subgraph where only edges were deleted. In a k-degenerate graph G every subgraph of G has a vertex of degree at most k. The degeneracy of a graph G is the minimum integer k such that G is k-degenerate. By deleting edges of a graph the degeneracy can be reduced. We introduce the term of k-degenerate skewness ds_k(G) that denotes the number of edges in a graph G that need to be deleted so that it becomes k-degenerate. We also define the maximum k-degenerate skewness ds_k^C(n) for a graph class C as the maximum of ds_k(G) over all graphs G in C with n vertices. We describe general methods to reduce the degeneracy of a graph. Furthermore, we give bounds for ds_k^P(n) and ds_k^B(n). Here, P stands for the graph class containing all planar graphs and B for the graph class containing all bipartite planar graphs.

Minimum Linear Arrangement

  • Datum: Fr, 12 Nov 2021, 14:30
  • Ort: SR 301
  • Vortragende(r): Michael, Zündorf, Master thesis introduction talk
  • Inhalt: TBD

A Novel Time-dependent Model for Route Planning in Public Transit Networks

  • Datum: Fr, 12 Nov 2021, 14:00
  • Ort: SR 301
  • Vortragende(r): Voula Machaira, Guest Talk; Master Thesis; University of Patras
  • Inhalt: In this thesis, the non-FIFO time-dependent model with REalistic vehicle eXchange times (REX) is introduced for schedule-based public transport systems, along with two novel query algorithms for computing optimal multimodal journeys for either a single criterion (earliest arrivals) or two criteria (plus number of transfers). The REX model is a considerable enhancement of the simple time-dependent model, with additional features towards handling non-negligible exchanges from one vehicle to another, as well as supporting non-FIFO instances which are typical in public transport, without compromising the space efficiency of the model. Apart from the novelty of the model, REX is also accompanied with two novel query algorithms, whose rationale is some sort of "trip-targeted" label-correction propagation process: the first algorithm, TRIP-based Label-correction propagation Algorithm (TRIPLA), efficiently solves the realistic earliest-arrival routing problem; the second algorithm, BI-criteria TRIP-based Label-correction propagation Algorithm (BITRIPLA), solves the bi-criteria variant of the problem, where apart from the earliest-arrival objective, the commuters also care for minimizing the number of vehicle exchanges. The set of Pareto-optimal journeys is discovered when all the arrival-times are bounded. We conduct a thorough experimental evaluation on real-world public transit networks which demonstrates that both query algorithms for the REX model are competitive with state-of-art query algorithms for multimodal routing in schedule-based public transport models.

Local Page Number und local Queue Number von gerichteten azyklischen Graphen

  • Datum: Fr, 29 Okt 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): Tim Groß, ITI Wagner; Bachelor Thesis
  • Inhalt: Ein Book Embedding (Queue Layout) eines gerichteten azyklischen Graphen besteht aus einer topologischen Ordnung seiner Knoten und einer Partition seiner Kanten in Seiten (Queues) genannte Teilmengen, sodass sich Kanten in derselben Seite (Queue) nicht kreuzen (verschachteln). Zwei Kanten kreuzen sich (sind verschachtelt), wenn ihre Endpunkte in einem ABAB (ABBA) Muster angeordnet sind. Die local Page Number pn(G) (local Queue Number qn(G)) eines Graphen G ist die kleinste Zahl k, sodass es ein Book Embedding (Queue Layout) für G gibt, in welchem jeder Knoten inzidente Kanten in höchstens k Seiten (Queues) hat. Wir präsentieren hier kurz die wichtigsten Ergebnisse der Bachelorarbeit zum Thema "Local Page Number und local Queue Number von gerichteten azyklischen Graphen". Wir zeigen jeweils die Konstruktion eines planaren Graphen mit local Page Number 3, sowie eines mit local Queue Number 3. Außerdem konstruieren wir einen planaren Graphen, der für eine feste Knotenordnung local Page Number 4 hat. Weiterhin zeigen wir für die local Page Number und die local Queue Number von planaren Graphen eine obere Schranke von 4. Für die local Page Number sowie die local Queue Number von gerichteten azyklischen k-Bäumen zeigen wir jeweils eine untere sowie obere Schranke von k+1.

Leiden-Based Parallel Community Detection

  • Datum: Fr, 22 Okt 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): Fabian Nguyen, ITI Wagner; Bachelor Thesis
  • Inhalt: Leiden is a community detection algorithm for maximizing modularity by dividing a graph into densely connected disjoint sets of nodes. It improves the well-known Louvain algorithm with an additional refinement phase in which clusters are subdivided before contraction. In this work we investigate an efficient parallelization of the refinement phase and build upon existing work on parallelizing the local moving phase. We show that the overall implementation achieves speedups up to 15.8 on the largest tested graph with 64 threads. Parallel refinement achieves speedups up to 28 with 128 threads whereas local moving only scales up to about 32 threads with a maximum speed up of 12.5.

Coloring the Union of Geometric Hypergraphs

  • Datum: Fr, 8 Okt 2021, 14:30
  • Ort: SR 301
  • Vortragende(r): Vera Chekan, ITI Wagner; Master Thesis
  • Inhalt: For a range family R (e.g., all axis-aligned rectangles in the plane) we consider a geometric hypergraph captured by R, i.e., its vertex set is a finite set of points in the plane and its hyperedges are such subsets of these points that are contained in some range in R. In this thesis we investigate the existence of polychromatic colorings for unions of geometric hypergraphs: in such a coloring every hyperedge contains a vertex of each color. For a range family R and number of colors k, the value m(k) is the smallest number such that every m(k)-uniform hypergraph captured by R admits a polychromatic coloring with k colors. We concentrate on range families consisting of various unbounded axis-aligned rectangles and diagonal strips of slope -1: for each subfamily we either provide an upper bound on m(k) or prove that m(2) = infinity holds. n particular, we show that for the family of all bottomless rectangles and horizontal strips we have m(2) = infinity.

On the Resolution of the Sensitivity Conjecture

  • Datum: Fr, 8 Okt 2021, 14:00
  • Ort: SR 301
  • Vortragende(r): David Schuldes, ITI Wagner; Bachelor Thesis
  • Inhalt: The sensitivity of a boolean function is defined as the maximum number of indices of any input vector x in {0, 1}^n such that flipping the input vector at the index changes the value of f(x). In my presentation I will outline the conceptual proof of the Sensitivity Conjecture and introduce the necessary mathematical definitions and theorems to do so. Moreover, I will show how the techniques used to prove the Sensitivity Conjecture can further be used in order to obtain insights into the structural relationships between a special class of matrices, their eigenvalues, the maximum degree of corresponding the graph and vertex induced subgraphs. Then I will show an additional insight into the relationship between vertex induced subgraphs of the n-hypercube and the structure of the node with maximum degree. To close the presentation, I will show an alternative proof of the main theorem that does not make use of matrices.

Sommersemester 2021

Analysis of Heuristics for Treewidth

  • Datum: Do, 30 Sep 2021, 15:30
  • Ort: ms teams
  • Vortragende(r): Marcus Wunderlich, ITI Blaesius; Bachelor Thesis
  • Inhalt: Treewidth is an important concept in many fields like for example, graph theory and parameterized algorithms. Determining a graph's treewidth is necessary for many applications, but it is, unfortunately, an NP-hard problem. To at least approximate the treewidth efficiently, several heuristics were introduced, including the MinDegree heuristic and the MinFillIn heuristic. Although these achieve surprisingly good results in practice, they are barely studied theoretically. In this thesis, we initiate this study by investigating the behavior of the two heuristics on grids. Along the way to grids with arbitrarily large side lengths, we also investigate some superclasses of small grids like the chordal graphs and series-parallel graphs. We additionally present a first approach to upper bound the result of the MinDegree heuristic, and introduce the concept of a border graph -- a simple structure that captures all relevant information at any fixed point in time during the execution of one of the heuristics. We believe that the border graph provides a useful perspective that will help future studies of the heuristics.

Applying Customizable Contraction Hierarchy Potentials to the Shortest Epsilon-Smooth Path Problem

  • Datum: Fr, 24 Sep 2021, 15:00
  • Ort: ms teams
  • Vortragende(r): Jakob Bussas, ITI Wagner; Bachelor Thesis
  • Inhalt: When computing traffic routes, it is important to consider real-time traffic data. However, this data is not always perfect and might lead to routes with unwanted detours, for example through residential areas. This work focuses on finding fast routes with real-time traffic data while avoiding such unwanted detours. The approach will be to find a shortest path with respect to two different edge weight functions. We propose an algorithm that makes use of Customizable Contraction Hierarchies and analyze its performance and behavior.

Planning Geometric Microgrid Cable Layouts

  • Datum: Fr, 24 Sep 2021, 14:30
  • Ort: ms teams
  • Vortragende(r): Max Göttlicher, ITI Wagner; Master Thesis
  • Inhalt: We introduce a new genetic algorithm for the Microgrid cabling problem. Microgrid cabling is the problem of finding a minimum cost cable layout for a microgrid given the consumer demands and generator supplies and their positions in the plane. The layout is a tree on the terminals and additional freely placeable Steiner nodes with cable types assigned to the edges. The layout cost depends on the required power capacities of the edges and the cable losses. Our algorithm explores possible cable layouts and uses a heuristic to assign the cables with respect to capacitites and losses. The genetic operators can be used in other geometric tree problems. Our algorithm finds good solutions to the geometric Steiner tree problems but cannot compete with dedicated algorithms. On a real-world microgrid example our algorithm converged in less than 30 seconds.

Tiling Rectangles with Unions of Squares

  • Datum: Fr, 24 Sep 2021, 14:00
  • Ort: SR 301
  • Vortragende(r): Jonas Seiler, ITI Wagner; Bachelor Thesis
  • Inhalt: Given two squares with side lengths a and b, we can "glue" them together to get an (a, b)-piece. A tiling of a rectangle with side lengths C and D with (a, b)-pieces is a placement of these pieces such that every point in the rectangle is covered by exactly one piece and no piece goes out of the rectangle. We show that we can decide whether a given C × D-rectangle can be tiled with (a, b)-pieces and we can at least semi decide whether there exists a C × D-rectangle that can be tiled with given (a, b)-pieces. Furthermore we will look at some pieces in detail and find categories that have no tilings and some that have at least one tiling. Lastly we will also prove that we can tile the whole plane with (a, b)-pieces for every combination of a,b.

Induced Universal Graphs for Edge-Colored Complete Graphs

  • Datum: Fr, 10 Sep 2021, 14:30
  • Ort: SR 301
  • Vortragende(r): Christian Kouekam, ITI Wagner; Master Thesis
  • Inhalt: TBA

Upward and Upward-Planar Drawings with Limited Slopes

  • Datum: Fr, 10 Sep 2021, 14:00
  • Ort: SR 301
  • Vortragende(r): Valentin Quapil, ITI Wagner; Bachelor Thesis
  • Inhalt: We present algorithms and limitations of upward and upward-planar drawings with a limited number of distinct slopes. First we discuss which slope sets are interchangable when drawing upward planar. Then we present a new algorithm for drawing series-parallel graphs upward planar with two or three slopes. Finally, we show a lower bound for the space requirements of upward planar drawings with three slopes: There are series-parallel graphs, cacti, and ordered trees whose upward planar drawings with three slopes require exponential width and height on the integer grid.

Engineering Heuristic Quasi-Threshold Editing

  • Datum: Fr, 23 Jul 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): David Schmitt, ITI Wagner; Master Thesis
  • Inhalt: We introduce an algorithm that solves the quasi-threshold graph editing problem. The problem is defined as removing and inserting edges in a graph to reach a quasi-threshold graph. Quasi-threshold graphs can be defined as the transitive closure of a rooted forest. Given a graph, the algorithm computes a quasi-threshold graph, which is close to the original regarding the sum of edge edit costs. Building on the previously introduced heuristic Quasi-Threshold Mover (QTM), which is limited to uniform edit costs, we consider edit costs for edge insertions and deletions. QTM represents the graph as a skeleton forest and works in rounds. In each round, QTM heuristically improves the number of edits by trying to move every node to a new position in the forest. The approach is called local move. We adapt QTM to solve the problem while minimizing edit costs. Additionally, we propose improvements in solution quality by moving nodes with their subtree instead of the node alone. This optimization is called subtree move. In an extensive experimental evaluation, we apply the algorithm to two large sets of graphs. The quality of the solution and running time per round of QTM suffers with edit costs considered in comparison to uniform edit costs. The solution quality can be improved by enabling the subtree move optimization at the cost of additional running time per round.

Robust Hypergraph Coarsening

  • Datum: Fr, 9 Jul 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): Simon Vögele, ITI Wagner; Bachelor Thesis
  • Inhalt: Balanced hypergraph partitioning is a NP-hard problem with applications in various domains like high performance computing and chip design. The multilevel heuristic is used by many partitioners to solve this problem. This heuristic splits the problem into three phases: coarsening, initial partitioning and uncoarsening. The coarsening phase creates a hierarchy of consecutively smaller hypergraphs. The initial partitioning phase computes a partition of the coarsest hypergraph in the hierarchy. In the uncoarsening phase, the partition is projected through the hierarchy and refined until a partition for the original hypergraph is found. We improve the coarsening phase of the hypergraph partitioning tool Mt-KaHyPar. This is done by relaxing some restrictions on how to coarsen the hypergraph if the coarsening does not achieve small enough coarse hypergraphs. Our experiments show that these improvements are able to reduce coarse hypergraph size by up to 98% and total partitioning runtime by up to 54% on some instances with no significant loss of solution quality.

Community Detection in Hypergraphs with Application to Partitioning

  • Datum: Di, 22 Jun 2021, 11:00
  • Ort: https://i10meeting.iti.kit.edu/AbschlussvortragKrause
  • Vortragende(r): Robert Krause, ITI Wagner und Sanders; Bachelor Thesis
  • Inhalt: We present different approaches to community detection on hypergraphs and evaluate them as a preprocessing step for the coarsening phase of a hypergraph partitioning algorithm. We present a modularity maximization approach that optimizes a modularity formulation that we derived by incorporating the connectivity of hyperedges. We optimize this hypergraph modularity using the parallel Louvain method. Additionally, we present formulations for the map equation on hypergraphs based on different random walk models. We integrate our hypergraph community detection algorithms into the parallel shared-memory hypergraph partitioner Mt-KaHyPar. Finally, we evaluate different optimizations and heuristics we used to speed up the hypergraph modularity method and compare our different approaches as well as the current graph-based approach in extensive experiments. Our approach produced better partitions than the current configuration Mt-KaHyPar-D on 61% of the instances. However, our approach is slower by a factor of 5.4 on average.

Improving Parallel Refinement Algorithms for Hypergraph Partitioning

  • Datum: Fr, 7 Mai 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): Noah Wahl, ITI Wagner; Bachelor Thesis
  • Inhalt: Hypergraph partitioning algorithms leverage fast local search algorithms to improve initial solutions, often within the multilevel framework. The most widely used local search algorithm is the Fiduccia-Mattheyses (FM) refinement heuristic, which repeatedly performs the vertex move that improves the solution quality the most, while maintaining a balanced partition. To escape local minima, it allows intermediate quality losses, but reverts to the best solution observed at the end of a pass. With the increasing importance of parallel processing, several parallelization approaches have been published in recent years. In this work, new and existing techniques to improve these algorithms are investigated. Further, the trade-offs between several design decisions of the two most prominent, recent parallelization approaches, the greedy refinement of Mt-Metis and localized FM of Mt-KaHyPar are experimentally evaluated. The implementation is integrated in the Mt-KaHyPar framework. Message queues lead to no noticeable difference in most cases, because the gain table of Mt-KaHyPar overshadows their utility. Greedy refinement suffers from a large discrepancy in solution quality induced by a fixed assignment of vertices. Delaying or preventing reoccurring expensive gain updates leads to substantial savings on a set of previously problematic instances for Mt-KaHyPar. Finally, local search scheduling is a technique aimed at emulating sequential FM. While this emulation is successful, the overall solution quality is worse than the baseline approach, though more careful scheduling rules may yield improvements yet.

Beschleunigtes LKW-Routing mit zeitabhängigen Fahrverboten

  • Datum: Fr, 30 Apr 2021, 14:30
  • Ort: ms teams
  • Vortragende(r): Julius Häcker, ITI Wagner; Bachelor Thesis
  • Inhalt: Routinganwendungen sind für uns heutzutage sehr wichtig und werden häufig genutzt. Für LKWs brauchen wir anderes Routing als für PKWs, da es für LKWs temporäre Fahrverbote gibt. Das können Nacht- oder Wochentagsfahrverbote sein, die ein großräumiges Gebiet betreffen, oder Fahrverbote für bestimmte Straßenabschnitte. Dazu gibt es für LKWs im Gegensatz zu PKWs gesetzlich geregelte Lenk- und Ruhezeiten. Das bedeutet, dass der Fahrer nach einer bestimmten Fahrzeit eine Pause machen muss. Daher können Pausen und das Anfahren von Parkplätzen nötig werden. Für sinnvolle LKW-Routen ist es also wichtig, dass temporäre Fahrverbote und Lenk- und Ruhezeiten bereits in der Routenplanung berücksichtigt werden. Die Qualität einer Pause hängt von der Qualität des Parkplatzes ab, auf dem die Pause gemacht wird. Daher kann es sinnvoll sein, einen größeren Umweg für einen Parkplatz besserer Qualität zu fahren. Dadurch entsteht ein Trade-Off für die Berechnung der Routen. In [KSWZ20] wurde ein Algorithmus vorgestellt, der diesen Trade-Off beim Routing berücksichtigt. Dabei werden keine Lenk- und Ruhezeiten berücksichtigt. Wir erweitern diesen Algorithmus zu einer bidirektionalen Suche, um stärkeres Pruning zu ermöglichen und dadurch die Laufzeit zu verbessern. Die Laufzeit konnte dabei bei einigen langsamen (>10s) Queries halbiert werden. Ansonsten konnten keine langsamen Queries wesentlich beschleunigt werden. Außerdem modifizieren wir den Algorithmus, um Lenk- und Ruhezeiten in einer vereinfachten Form zu berücksichtigen. Dabei vereinfachen sich die Ergebnisse einiger Queries, sodass es dort weniger berechnete Routen gibt.

Coordinated Motion Planning for Multiple Square-Shaped Robots in a Grid

  • Datum: Fr, 30 Apr 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): Julian Dinh, ITI Wagner; Bachelor Thesis
  • Inhalt: Gegeben seien n quadratische Roboter mit Start- und Zielpositionen für jeden Roboter. Die Roboter befinden sich in einem unbegrenzten Gitter, welches stationäre Hindernisse enthalten kann. In jedem Zeitschritt kann sich ein Roboter in eine benachbarte Gitterposition bewegen oder auf seiner Position bleiben. Die Aufgabe ist es, einen Plan für die Bewegungsabläufe zu finden, in dem jeder Roboter an seiner Startposition beginnt und seine Zielposition erreicht, ohne dabei mit anderen Robotern oder Hindernissen zu kollidieren. Wir zeigen, dass wir mit einer kleinen Einschränkung immer einen solchen Plan finden. Zusätzlich möchten wir einerseits die Gesamtzeit, die benötigt wird, um alle Roboter an ihre Zielposition zu bringen, und andererseits die Strecke, die alle Roboter zusammen zurücklegen, minimieren. Wir betrachten diverse Heuristiken und evaluieren unsere Lösung auf verschiedenen Probleminstanzen.

A Shortest Path Approach for Gas Turbine Scheduling in Multimodal Energy Systems

  • Datum: Mo, 26 Apr 2021, 10:00
  • Ort: ms teams
  • Vortragende(r): Patrick Fetzer, ITI Wagner; Bachelor Thesis
  • Inhalt: Finding an optimal operating schedule for a combined heat and power plant in a multimodal energy system with district heating, photovoltaics and storages is challenging. The goal of this thesis is to compute an optimal day-ahead operating schedule for the gas turbine. With such a schedule the heat demand needs to be covered at all times, while thermal and electrical turbine output can be stored up to the capacities of the storages and surplus electrical power can be exported. A gas turbine schedule is called optimal if it fulfills demand and storage constraints while minimizing the operating costs. In this work a graph is constructed that represents states of charges of battery and heat storages with state transitions given by discrete thermal set points of the turbine. Two shortest path algorithms, a Dijkstra-based approach and a Dynamic Program, are used to find optimal gas turbine schedules. The algorithms are evaluated using a more accurate simulation of a district energy system scenario containing 16 buildings.

Effiziente Berechnung von Alternativrouten mit der Penaltymethode und CH-Potentialen

  • Datum: Fr, 16 Apr 2021, 14:00
  • Ort: ms teams
  • Vortragende(r): Max Willich, ITI Wagner; Bachelor Thesis
  • Inhalt: Wir beschäftigen uns mit der Berechnung von Alternativrouten von A nach B auf Straßengraphen. Mithilfe der Penalty-Methode können Graphen auf sogenannte Alternativgraphen reduziert werden. Ein guter Alternativgraph ist sehr dünn besetzt, beinhält aber viele gute Alternativrouten. Kobitzsch et al. veröffentlichten 2013 in [KRS13] eine Implementation der Penalty-Methode, welche sehr gute Alternativgraphen innerhalb weniger hundert Millisekunden berechnen kann. Wir evaluieren eine alternative Realisierung mithilfe des A*-Algorithmus und CH-Potentialen, welche einfacher zu implementieren ist, auf Qualität und Laufzeit. Wir erreichen hohe Erfolgsquoten und Pfadqualitäten für alle Testinstanzen. Wir erzielen schlechtere Laufzeiten als Kobitzsch et al., aber dennoch Laufzeiten unter einer Sekunde für alle außer die längsten Anfragen.