research
∙
07/03/2023
Complexity Dichotomies for the Maximum Weighted Digraph Partition Problem
We introduce and study a new optimization problem on digraphs, termed Ma...
share
research
∙
05/11/2023
Complexity of Efficient Outcomes in Binary-Action Polymatrix Games with Implications for Coordination Problems
We investigate the difficulty of finding economically efficient solution...
research
∙
04/20/2023
Bounds on Maximum Weight Directed Cut
We obtain lower and upper bounds for the maximum weight of a directed cu...
research
∙
10/14/2022
(1,1)-Cluster Editing is Polynomial-time Solvable
A graph H is a clique graph if H is a vertex-disjoin union of cliques. A...
research
∙
07/25/2022
Results on the Small Quasi-Kernel Conjecture
A quasi-kernel of a digraph D is an independent set Q⊆ V(D) such that fo...
research
∙
12/31/2021
Preference Swaps for the Stable Matching Problem
An instance I of the Stable Matching Problem (SMP) is given by a biparti...
research
∙
05/01/2021
Perfect Forests in Graphs and Their Extensions
Let G be a graph on n vertices. For i∈{0,1} and a connected graph G, a s...
research
∙
04/12/2021
Lower Bounds for Maximum Weighted Cut
While there have been many results on lower bounds for Max Cut in unweig...
research
∙
07/06/2020
Non-separating spanning trees and out-branchings in digraphsof independence number 2
A subgraph H= (V, F) of a graph G= (V,E) is non-separating if G-F, that ...
research
∙
03/16/2020
On the parameterized complexity of 2-partitions
We give an FPT algorithm for deciding whether the vertex set a digraph D...
research
∙
08/19/2019
Safe sets in digraphs
A non-empty subset S of the vertices of a digraph D is called a safe se...
research
∙
07/01/2019
The directed 2-linkage problem with length constraints
The weak 2-linkage problem for digraphs asks for a given digraph and ve...
research
∙
06/30/2019
Connecting edge-colouring
This paper studies the problem of connecting edge-colouring. Given an un...
research
∙
03/28/2019
Arc-disjoint Strong Spanning Subdigraphs of Semicomplete Compositions
A strong arc decomposition of a digraph D=(V,A) is a decomposition of it...
research
∙
03/01/2018
