9 papers · 1 filter
Designing Approximate Binary Trees for Trees
Leon Kellerhals, Mitja Krebs, André Nichterlein +1
We study the following problem that is motivated by demand-aware network design: Given a tree~, the task is to find a binary tree~ on the same vertex set. The objective is to…
The Harmonic Policy for Online Buffer Sharing is (2 + ln n)-Competitive: A Simple Proof
Vamsi Addanki, Julien Dallot, Leon Kellerhals +2
The problem of online buffer sharing is expressed as follows. A switch with output ports receives a stream of incoming packets. When an incoming packet is accepted by the switc…
The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
Matthias Bentert, Leon Kellerhals, Rolf Niedermeier
We study the parameterized complexity of finding shortest s-t-paths with an additional fairness requirement. The task is to compute a shortest path in a vertex-colored graph where…
Structural Parameterizations of the Biclique-Free Vertex Deletion Problem
Lito Goldmann, Leon Kellerhals, Tomohiro Koana
In this work, we study the Biclique-Free Vertex Deletion problem: Given a graph and integers and , find a set of at most vertices that intersects every (not ne…
Optimal Virtual Network Embeddings for Tree Topologies
Aleksander Figiel, Leon Kellerhals, Rolf Niedermeier +3
The performance of distributed and data-centric applications often critically depends on the interconnecting network. Applications are hence modeled as virtual networks, also accou…
Parameterized Algorithms for Diverse Multistage Problems
Leon Kellerhals, Malte Renken, Philipp Zschoche
The world is rarely static -- many problems need not only be solved once but repeatedly, under changing conditions. This setting is addressed by the "multistage" view on computatio…