research
∙
06/09/2023
Optimal distance query reconstruction for graphs without long induced cycles
Let G=(V,E) be an n-vertex connected graph of maximum degree Δ. Given ac...
share
research
∙
03/12/2023
Reconstructing Graphs from Connected Triples
We introduce a new model of indeterminacy in graphs: instead of specifyi...
research
∙
01/13/2023
Bridging the Gap Between Single and Multi Objective Games
A classic model to study strategic decision making in multi-agent system...
research
∙
06/23/2022
On the parameterized complexity of computing tree-partitions
We study the parameterized complexity of computing the tree-partition-wi...
research
∙
06/23/2022
On the Complexity of Problems on Tree-structured Graphs
In this paper, we introduce a new class of parameterized problems, which...
research
∙
06/20/2022
List Colouring Trees in Logarithmic Space
We show that List Colouring can be solved on n-vertex trees by a determi...
research
∙
01/31/2022
XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure
In this paper, we show several parameterized problems to be complete for...
research
∙
10/06/2021
Tight bounds for counting colorings and connected edge sets parameterized by cutwidth
We study the fine-grained complexity of counting the number of colorings...
research
∙
08/05/2021
A tight local algorithm for the minimum dominating set problem in outerplanar graphs
We show that there is a deterministic local algorithm (constant-time dis...
research
∙
06/30/2021
Parameterized Complexities of Dominating and Independent Set Reconfiguration
We settle the parameterized complexities of several variants of independ...
research
∙
05/31/2021
Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space
Let XNLP be the class of parameterized problems such that an instance of...
research
∙
12/04/2020
Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces
The asymptotic dimension is an invariant of metric spaces introduced by ...
research
∙
12/03/2020
Optimal labelling schemes for adjacency, comparability and reachability
We construct asymptotically optimal adjacency labelling schemes for ever...
research
∙
08/03/2020
Approximating pathwidth for graphs of small treewidth
We describe a polynomial-time algorithm which, given a graph G with tree...
research
∙
04/19/2018
The Curse of Ties in Congestion Games with Limited Lookahead
We introduce a novel framework to model limited lookahead in congestion ...
research
∙
03/14/2018