23 citations · 76 across the 30 of their papers we have counts for
4 papers · 2 filters
On independent set on B1-EPG graphs
Marin Bougeret, Stephane Bessy, Daniel Gonçalves +1
In this paper we consider the Maximum Independent Set problem (MIS) on -EPG graphs. EPG (for Edge intersection graphs of Paths on a Grid) was introduced in ~\cite{edgeintersin…
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…
An FPT algorithm and a polynomial kernel for Linear Rankwidth-1 Vertex Deletion
Mamadou Moustapha Kanté, Eun Jung Kim, O-joung Kwon +1
Linear rankwidth is a linearized variant of rankwidth, introduced by Oum and Seymour [Approximating clique-width and branch-width. J. Combin. Theory Ser. B, 96(4):514--528, 2006].…