23 citations · 60 across the 50 of their papers we have counts for
7 papers · 1 filter
Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs
Luerbio Faria, Sulamita Klein, Ignasi Sau +1
A graph is signed if each edge is assigned or . A signed graph is balanced if there is a bipartition of its vertex set such that an edge has sign if and only if its…
An -approximation for covering and packing minor models of
Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau +1
Given two graphs and , we define (resp. ) as the minimum number of vertices (resp. edges) whose removal from produces…
Minors in graphs of large -girth
Dimitris Chatzidimitriou, Jean-Florent Raymond, Ignasi Sau +1
For every , let denote the graph with two vertices and parallel edges. The -girth of a graph is the minimum number of edges of a subgraph of $G…
Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism
Eunjung Kim, Christophe Paul, Ignasi Sau +1
In this paper we design {\sf FPT}-algorithms for two parameterized problems. The first is \textsc{List Digraph Homomorphism}: given two digraphs and and a list of allowed v…
An FPT 2-Approximation for Tree-Cut Decomposition
Eunjung Kim, Sang-il Oum, Christophe Paul +2
The tree-cut width of a graph is a graph parameter defined by Wollan [J. Comb. Theory, Ser. B, 110:47-66, 2015] with the help of tree-cut decompositions. In certain cases, tree-cut…
Parameterized complexity dichotomy for -Vertex Deletion
Julien Baste, Luerbio Faria, Sulamita Klein +1
For two integers , a graph is an -graph if can be partitioned into independent sets and cliques. In the parameterized $(r,\ell…