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...
share
research
∙
03/13/2023
Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
We investigate a relaxation of the notion of treewidth-fragility, namely...
research
∙
08/11/2022
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification
In the Directed Steiner Network problem, the input is a directed graph G...
research
∙
08/04/2022
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
The leafage of a chordal graph G is the minimum integer l such that G ca...
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
∙
05/25/2022
The complexity of blocking (semi)total dominating sets with edge contractions
We consider the problem of reducing the (semi)total domination number of...
research
∙
05/20/2022
Parameterized Complexity of Weighted Multicut in Trees
The Edge Multicut problem is a classical cut problem where given an undi...
research
∙
07/08/2021
Using edge contractions to reduce the semitotal domination number
In this paper, we consider the problem of reducing the semitotal dominat...
research
∙
10/27/2020
Reducing the domination number of P_3+kP_2-free graphs via one edge contraction
In this note, we consider the following problem: given a connected graph...
research
∙
09/18/2020
Blocking total dominating sets via edge contractions
In this paper, we study the problem of deciding whether the total domina...
research
∙
04/16/2020
Approximating Independent Set and Dominating Set on VPG graphs
We consider Independent Set and Dominating Set restricted to VPG graphs ...
research
∙
09/13/2019
Characterising circular-arc contact B_0-VPG graphs
A contact B_0-VPG graph is a graph for which there exists a collection o...
research
∙
06/28/2019
Blocking dominating sets for H-free graphs via edge contractions
In this paper, we consider the following problem: given a connected grap...
research
∙
03/05/2019
CPG graphs: Some structural and hardness results
In this paper we continue the systematic study of Contact graphs of Path...
research
∙
03/05/2019
Reducing the domination number of graphs via edge contractions
In this paper, we study the following problem: given a connected graph G...
research
∙
01/07/2019
On the Parameterized Complexity of k-Edge Colouring
For every fixed integer k ≥ 1, we prove that k-Edge Colouring is fixed-p...
research
∙
10/18/2018
Planar CPG graphs
We show that for any k ≥ 0, there exists a planar graph which is B_k+1-C...
research
∙
10/16/2018
Semitotal Domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width
A semitotal dominating set of a graph G with no isolated vertex is a dom...
research
∙
10/10/2018
Classifying k-Edge Colouring for H-free Graphs
A graph is H-free if it does not contain an induced subgraph isomorphic ...
research
∙
08/28/2018
Proper circular arc graphs as intersection graphs of paths on a grid
In this paper we present a characterisation, by an infinite family of mi...
research
∙
03/09/2018
