12 papers
Determining the Complexity of Chromatic Sum in Classes Defined by a Set of Forbidden Graphs
Clément Dallard, Daniël Paulusma, Erik Jan van Leeuwen
The Chromatic Sum problem asks, given a graph and an integer , whether admits a colouring with sum . We study the complexity of Chromatic S…
Beyond Parents? Prediction Gaps in University Completion Using Population-Scale Networks and Flexible Machine Learning
Javier Garcia-Bernardo, Eva Jaspers, Weverthon Machado +2
How much of children's educational attainment remains predictable from the wider social contexts in which they grow up, once parental background is known? Sociological research pla…
Colouring Probe -Free Graphs
Daniël Paulusma, Johannes Rauch, Erik Jan van Leeuwen
The NP-complete problems Colouring and k-Colouring ) are well studied on -free graphs, i.e., graphs that do not contain some fixed graph as an induced subgraph. We…
The Complexity of Diameter on H-free graphs
Jelle J. Oostveen, Daniël Paulusma, Erik Jan van Leeuwen
The intensively studied Diameter problem is to find the diameter of a given connected graph. We investigate, for the first time in a structured manner, the complexity of Diameter f…
The Parameterised Complexity of Integer Multicommodity Flow
Hans L. Bodlaender, Isja Mannens, Jelle J. Oostveen +2
The Integer Multicommodity Flow problem has been studied extensively in the literature. However, from a parameterised perspective, mostly special cases, such as the Disjoint Paths…
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Benjamin Bergougnoux, Vera Chekan, Robert Ganian +5
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simpl…