38 citations · 189 across the 43 of their papers we have counts for
6 papers · 1 filter
Complexity and Approximability of Parameterized MAX-CSPs
Holger Dell, Eun Jung Kim, Michael Lampis +2
We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity; the goal is to compute the maximum fraction of constr…
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…
The "art of trellis decoding" is fixed-parameter tractable
Jisu Jeong, Eun Jung Kim, Sang-il Oum
Given n subspaces of a finite-dimensional vector space over a fixed finite field , we wish to find a linear layout of the subspaces such that $\dim(…
A polynomial kernel for Block Graph Deletion
Eun Jung Kim, O-joung Kwon
In the Block Graph Deletion problem, we are given a graph on vertices and a positive integer , and the objective is to check whether it is possible to delete at most …
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].…