research
∙
07/18/2023
Algorithms and hardness for Metric Dimension on digraphs
In the Metric Dimension problem, one asks for a minimum-size set R of ve...
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/12/2023
Complexity of conjunctive regular path query homomorphisms
A graph database is a digraph whose arcs are labeled with symbols from a...
research
∙
02/04/2023
Extremal digraphs for open neighbourhood location-domination and identifying codes
A set S of vertices of a digraph D is called an open neighbourhood locat...
research
∙
01/31/2023
New bounds and constructions for neighbor-locating colorings of graphs
A proper k-coloring of a graph G is a neighbor-locating k-coloring if fo...
research
∙
01/10/2023
Neighbourhood complexity of graphs of bounded twin-width
We give essentially tight bounds for, ν(d,k), the maximum number of dist...
research
∙
12/31/2022
Isometric path complexity of graphs
We introduce and study a new graph parameter, called the isometric path ...
research
∙
12/22/2022
Parameterizing Path Partitions
We study the algorithmic complexity of partitioning the vertex set of a ...
research
∙
11/25/2022
Progress towards the two-thirds conjecture on locating-total dominating sets
We study upper bounds on the size of optimum locating-total dominating s...
research
∙
11/15/2022
The RED-BLUE SEPARATION problem on graphs
We introduce the Red-Blue Separation problem on graphs, where we are giv...
research
∙
06/30/2022
On graphs coverable by k shortest paths
We show that if the edges or vertices of an undirected graph G can be co...
research
∙
10/26/2021
Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
The Grundy number of a graph is the maximum number of colours used by th...
research
∙
04/16/2021
Complexity and algorithms for injective edge-coloring in graphs
An injective k-edge-coloring of a graph G is an assignment of colors, i....
research
∙
10/30/2020
Monitoring the edges of a graph using distances
We introduce a new graph-theoretic concept in the area of network monito...
research
∙
09/22/2020
Discriminating Codes in Geometric Setups
We study two geometric variations of the discriminating code problem. In...
research
∙
09/02/2020
Exact square coloring of subcubic planar graphs *
We study the exact square chromatic number of subcubic planar graphs. An...
research
∙
06/30/2020
Algorithms and complexity for geodetic sets on planar and chordal graphs
We study the complexity of finding the geodetic number on subclasses of ...
research
∙
03/23/2020
On the complexity of Broadcast Domination and Multipacking in digraphs
We study the complexity of the two dual covering and packing distance-ba...
research
∙
10/11/2019
Domination and location in twin-free digraphs
A dominating set D in a digraph is a set of vertices such that every ver...
research
∙
10/02/2019
Parameterized complexity of edge-coloured and signed graph homomorphism problems
We study the complexity of graph modification problems for homomorphism-...
research
∙
09/19/2019
Hardness and approximation for the geodetic set problem in some graph classes
In this paper, we study the computational complexity of finding the geod...
research
∙
07/07/2019
Complexity of planar signed graph homomorphisms to cycles
We study homomorphism problems of signed graphs. A signed graph is an un...
research
∙
12/20/2018