research
∙
09/06/2023
Non-Clashing Teaching Maps for Balls in Graphs
Recently, Kirkpatrick et al. [ALT 2019] and Fallat et al. [JMLR 2023] in...
share
research
∙
07/16/2023
Tight (Double) Exponential Bounds for NP-Complete Problems: Treewidth and Vertex Cover Parameterizations
Treewidth is as an important parameter that yields tractability for many...
research
∙
05/26/2023
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
For a well-studied family of domination-type problems, in bounded-treewi...
research
∙
05/11/2023
Minimal dominating sets enumeration with FPT-delay parameterized by the degeneracy and maximum degree
At STOC 2002, Eiter, Gottlob, and Makino presented a technique called or...
research
∙
02/21/2023
Complexity of Maker-Breaker Games on Edge Sets of Graphs
We initiate the study of the algorithmic complexity of Maker-Breaker gam...
research
∙
11/08/2022
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs
We investigate how efficiently a well-studied family of domination-type ...
research
∙
06/30/2022
Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
For a graph G, a subset S ⊆ V(G) is called a resolving set if for any tw...
research
∙
06/27/2022
Sample compression schemes for balls in graphs
One of the open problems in machine learning is whether any set-family o...
research
∙
03/08/2020
The Game of Cops and Eternal Robbers
We introduce the game of Cops and Eternal Robbers played on graphs, wher...
research
∙
03/03/2020