research
∙
09/14/2023
Dynamic programming on bipartite tree decompositions
We revisit a graph width parameter that we dub bipartite treewidth, alon...
share
research
∙
01/24/2023
Treewidth is NP-Complete on Cubic Graphs (and related results)
In this paper, we give a very simple proof that Treewidth is NP-complete...
research
∙
09/16/2022
b-Coloring Parameterized by Pathwidth is XNLP-complete
We show that the b-Coloring problem is complete for the class XNLP when ...
research
∙
07/15/2022
A tight quasi-polynomial bound for Global Label Min-Cut
We study a generalization of the classic Global Min-Cut problem, called ...
research
∙
07/15/2022
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
We show fixed-parameter tractability of the Directed Multicut problem wi...
research
∙
05/02/2022
Taming graphs with no large creatures and skinny ladders
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: i...
research
∙
02/27/2022
A logic-based algorithmic meta-theorem for mim-width
We introduce a logic called distance neighborhood logic with acyclicity ...
research
∙
09/28/2021
A Unifying Framework for Characterizing and Computing Width Measures
Algorithms for computing or approximating optimal decompositions for dec...
research
∙
05/04/2021
Classes of intersection digraphs with good algorithmic properties
An intersection digraph is a digraph where every vertex v is represented...
research
∙
09/09/2020
Diverse Pairs of Matchings
We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matching...
research
∙
05/10/2020
Structural Parameterizations of Clique Coloring
A clique coloring of a graph is an assignment of colors to its vertices ...
research
∙
03/09/2020
b-Coloring Parameterized by Clique-Width
We provide a polynomial-time algorithm for b-Coloring on graphs of const...
research
∙
02/25/2020
Hedonic Seat Arrangement Problems
In this paper, we study a variant of hedonic games, called Seat Arrangem...
research
∙
02/25/2020
Well-partitioned chordal graphs: obstruction set and disjoint paths
We introduce a new subclass of chordal graphs that generalizes split gra...
research
∙
01/15/2020
Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach
It can be shown that each permutation group G S_n can be embedded, in a...
research
∙
11/12/2019
FPT Algorithms for Diverse Collections of Hitting Sets
In this work, we study the d-Hitting Set and Feedback Vertex Set problem...
research
∙
05/09/2019
Typical Sequences Revisited - Algorithms for Linear Orderings of Series Parallel Digraphs
In this paper, we show that the Cutwidth, Modified Cutwidth, and Vertex ...
research
∙
03/18/2019
Diversity in Combinatorial Optimization
When modeling an application of practical relevance as an instance of a ...
research
∙
11/23/2018
What is known about Vertex Cover Kernelization?
We are pleased to dedicate this survey on kernelization of the Vertex Co...
research
∙
11/09/2018
A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs
A b-coloring of a graph G is a proper coloring of its vertices such that...
research
∙
03/09/2018
Generalized distance domination problems and their complexity on graphs of bounded mim-width
We generalise the family of (σ, ρ)-problems and locally checkable vertex...
research
∙
11/14/2017