research
∙
08/08/2023
On the Complexity of Finding a Sparse Connected Spanning Subgraph in a non-Uniform Failure Model
We study a generalization of the classic Spanning Tree problem that allo...
share
research
∙
05/02/2023
Two-sets cut-uncut on planar graphs
We study the following Two-Sets Cut-Uncut problem on planar graphs. Ther...
research
∙
05/16/2022
Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences
We study stable matching problems where agents have multilayer preferenc...
research
∙
05/11/2022
Who won? Winner Determination and Robustness in Liquid Democracy
Liquid democracy is a decision-making paradigm in which each agent can e...
research
∙
03/31/2022
Finding Balance-Fair Short Paths in Graphs
The computation of short paths in graphs with edge lengths is a pillar o...
research
∙
02/26/2021
A Multivariate Complexity Analysis of the Material Consumption Scheduling Problem
The NP-hard MATERIAL CONSUMPTION SCHEDULING Problem and closely related ...
research
∙
02/17/2021
The Complexity of Gerrymandering Over Graphs: Paths and Trees
Roughly speaking, gerrymandering is the systematic manipulation of the b...
research
∙
07/24/2020
Using a geometric lens to find k disjoint shortest paths
Given an undirected n-vertex graph and k pairs of terminal vertices (s_1...
research
∙
05/29/2020
Parameterized Complexity of Min-Power Asymmetric Connectivity
We investigate parameterized algorithms for the NP-hard problem Min-Powe...
research
∙
05/05/2020
On Reachable Assignments in Cycles and Cliques
The efficient and fair distribution of indivisible resources among agent...
research
∙
10/08/2019
Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters
In the presented paper we study the Length-Bounded Cut problem for speci...
research
∙
10/01/2019
Polynomial-Time Preprocessing for Weighted Problems Beyond Additive Goal Functions
Kernelization is the fundamental notion for polynomial-time prepocessing...
research
∙
08/30/2019
Efficient Computation of Optimal Temporal Walks under Waiting-Time Constraints
Node connectivity plays a central role in temporal network analysis. We ...
research
∙
05/10/2019
Good Things Come to Those Who Swap Objects on Paths
We study a simple exchange market, introduced by Gourvés, Lesca and Wilc...
research
∙
01/30/2019
Comparing Election Methods Where Each Voter Ranks Only Few Candidates
Election rules are formal processes that aggregate voters preferences, t...
research
∙
06/26/2018
Listing All Maximal k-Plexes in Temporal Graphs
Social networks evolve over time, that is, new contacts appear and old c...
research
∙
02/27/2018
Parameterized Complexity of Diameter
Diameter--the task of computing the length of a longest shortest path---...
research
∙
02/19/2018
Towards Improving Brandes' Algorithm for Betweenness Centrality
Betweenness centrality, measuring how many shortest paths pass through a...
research
∙
12/18/2017