research
∙
09/08/2023
Shortest Path with Positive Disjunctive Constraints – a Parameterized Perspective
We study the SHORTEST PATH problem with positive disjunctive constraints...
share
research
∙
08/02/2023
Polynomial-delay Enumeration Kernelizations for Cuts of Bounded Degree
Enumeration kernelization was first proposed by Creignou et al. [TOCS 20...
research
∙
03/05/2023
Expansion Lemma – Variations and Applications to Polynomial-Time Preprocessing
In parameterized complexity, it is well-known that a parameterized probl...
research
∙
12/01/2022
An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set
We study the CONNECTED η-TREEDEPTH DELETION problem where the input inst...
research
∙
01/10/2022
Deletion to Scattered Graph Classes II – Improved FPT Algorithms for Deletion to Pairs of Graph Classes
Let Π be a hereditary graph class. The problem of deletion to Π, takes a...
research
∙
06/10/2021
Valued Authorization Policy Existence Problem: Theory and Experiments
Recent work has shown that many problems of satisfiability and resilienc...
research
∙
05/10/2021
Parameterized Complexity of Deletion to Scattered Graph Classes
Graph-modification problems, where we add/delete a small number of verti...
research
∙
04/13/2021
Towards Better Understanding of User Authorization Query Problem via Multi-variable Complexity Analysis
User authorization queries in the context of role-based access control h...
research
∙
09/17/2020
p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms
We introduce and study two natural generalizations of the Connected Vert...
research
∙
07/28/2019
Parameterized Pre-coloring Extension and List Coloring Problems
Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the p...
research
∙
05/08/2019
On the Approximate Compressibility of Connected Vertex Cover
The Connected Vertex Cover problem, where the goal is to compute a minim...
research
∙
04/15/2019
Bounded and Approximate Strong Satisfiability in Workflows
There has been a considerable amount of interest in recent years in the ...
research
∙
11/12/2018
Tractability of Konig Edge Deletion Problems
A graph is said to be a Konig graph if the size of its maximum matching ...
research
∙
11/21/2017