11 citations · 15 across the 15 of their papers we have counts for
19 papers
Parameterizing Cluster Editing by the Number of Deletions
Vincent Froese, Leon Kellerhals, Frank Sommer +2
In Cluster Editing, we are given a graph and an integer and ask whether at most edge insertions and deletions turn into a disjoint union of cliques. Komusiewicz and…
PeakBench: Benchmarking Resource-Aware Tool Invocation in LLM Agents
Zhi-Kai Chen, Xu-Xiang Zhong, Song-Yan Li +2
LLM agents increasingly solve tasks by invoking multiple tools, where parallel execution is essential for low latency but difficult to manage safely. Existing agent benchmarks prim…
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…
How to Resolve Envy by Adding Goods
Matthias Bentert, Robert Bredereck, Eva Deltl +2
We consider the problem of resolving the envy of a given initial allocation by adding elements from a pool of goods. We give a characterization of the instances where envy can be r…
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…
Parameterized Algorithms for Colored Clustering
Leon Kellerhals, Tomohiro Koana, Pascal Kunz +1
In the Colored Clustering problem, one is asked to cluster edge-colored (hyper-)graphs whose colors represent interaction types. More specifically, the goal is to select as many ed…
Single-Peaked Opinion Updates
Robert Bredereck, Anne-Marie George, Jonas Israel +1
We consider opinion diffusion for undirected networks with sequential updates when the opinions of the agents are single-peaked preference rankings. Our starting point is the study…
Fair Short Paths in Vertex-Colored Graphs
Matthias Bentert, Leon Kellerhals, Rolf Niedermeier
The computation of short paths in graphs with arc lengths is a pillar of graph algorithmics and network science. In a more diverse world, however, not every short path is equally v…
Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees
Leon Kellerhals, Tomohiro Koana, Pascal Kunz
Vertex Cover parameterized by the solution size k is the quintessential fixed-parameter tractable problem. FPT algorithms are most interesting when the parameter is small. Several…
Modification-Fair Cluster Editing
Vincent Froese, Leon Kellerhals, Rolf Niedermeier
The classic Cluster Editing problem (also known as Correlation Clustering) asks to transform a given graph into a disjoint union of cliques (clusters) by a small number of edge mod…
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…
A comparison between D-wave and a classical approximation algorithm and a heuristic for computing the ground state of an Ising spin glass
Ran Yaacoby, Nathan Schaar, Leon Kellerhals +3
Finding the ground state of an Ising-spin glass on general graphs belongs to the class of NP-hard problems, widely believed to have no efficient polynomial-time algorithms for solv…
Approximating Sparse Quadratic Programs
Danny Hermelin, Leon Kellerhals, Rolf Niedermeier +1
Given a matrix , we consider the problem of maximizing subject to the constraint . This problem, called MaxQP by Charikar an…
Parameterized Complexity of Geodetic Set
Leon Kellerhals, Tomohiro Koana
A vertex set of a graph is geodetic if every vertex of lies on a shortest path between two vertices in . Given a graph and , the NP-hard Geodeti…
An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
Matthias Bentert, Alexander Dittmann, Leon Kellerhals +2
Betweenness centrality---measuring how many shortest paths pass through a vertex---is one of the most important network analysis concepts for assessing the relative importance of a…
On the Computational Complexity of Variants of Combinatorial Voter Control in Elections
Leon Kellerhals, Viatcheslav Korenwein, Philipp Zschoche +2
Voter control problems model situations in which an external agent tries toaffect the result of an election by adding or deleting the fewest number of voters. The goal of the agent…