2 citations · 4 across the 10 of their papers we have counts for
11 papers
Complexity and Manipulation of International Kidney Exchange Programmes with Country-Specific Parameters
Rachael Colley, David Manlove, Daniel Paulusma +1
Kidney Exchange Programmes (KEPs) facilitate the exchange of kidneys, and larger pools of recipient-donor pairs tend to yield proportionally more transplants, leading to the propos…
Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
Felicia Lucke, Ali Momeni, Daniël Paulusma +1
The d-Cut problem is to decide if a graph has an edge cut such that each vertex has at most d neighbours at the opposite side of the cut. If , we obtain the intensively studie…
Graph Homomorphism, Monotone Classes and Bounded Pathwidth
Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma +1
In recent work by Johnson et al. (2022), a framework was described for the study of graph problems over classes specified by omitting each of a finite set of graphs as subgraphs. I…
Maximizing Matching Cuts
Van Bang Le, Felicia Lucke, Daniël Paulusma +1
A matching cut in a graph G is an edge cut of G that is also a matching. This short survey gives an overview of old and new results and open problems for Maximum Matching Cut, whic…
Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem
Hans L. Bodlaender, Matthew Johnson, Barnaby Martin +5
We study Steiner Forest on -subgraph-free graphs, that is, graphs that do not contain some fixed graph as a (not necessarily induced) subgraph. We are motivated by a recent…
Dichotomies for Maximum Matching Cut: -Freeness, Bounded Diameter, Bounded Radius
Felicia Lucke, Daniël Paulusma, Bernard Ries
The (Perfect) Matching Cut problem is to decide if a graph has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of . Both Matching Cut and Perfe…
Matching Cuts in Graphs of High Girth and H-Free Graphs
Carl Feghali, Felicia Lucke, Daniel Paulusma +1
The (Perfect) Matching Cut problem is to decide if a connected graph has a (perfect) matching that is also an edge cut. The Disconnected Perfect Matching problem is to decide if a…
Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-graphs
Vadim Lozin, Barnaby Martin, Sukanya Pandey +4
For a fixed set of graphs, a graph is -subgraph-free if does not contain any as a (not necessarily induced) subgraph. A recently propo…
On The Complexity of Matching Cut for Graphs of Bounded Radius and -Free Graphs
Felicia Lucke, Daniël Paulusma, Bernard Ries
For a connected graph , a matching is a matching cut of if is disconnected. It is known that for an integer , the corresponding decision proble…
Colouring Generalized Claw-Free Graphs and Graphs of Large Girth: Bounding the Diameter
Barnaby Martin, Daniel Paulusma, Siani Smith
For a fixed integer, the -Colouring problem is to decide if the vertices of a graph can be coloured with at most colours for an integer , such that no two adjacent vertic…
Computing Balanced Solutions for Large International Kidney Exchange Schemes
Márton Benedek, Péter Biró, Daniël Paulusma +1
To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient-donor pools.…