b'Eun Jung Kim'

research

∙ 08/31/2022

On weighted graph separation problems and flow-augmentation

One of the first application of the recently introduced technique of flo...

0 Eun Jung Kim, et al. ∙

research

∙ 07/15/2022

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints

We study the parameterized problem of satisfying “almost all” constraint...

0 Eun Jung Kim, et al. ∙

research

∙ 06/01/2022

Algorithmic Applications of Tree-Cut Width

The recently introduced graph parameter tree-cut width plays a similar r...

0 Robert Ganian, et al. ∙

research

∙ 04/01/2022

Twin-width VIII: delineation and win-wins

We introduce the notion of delineation. A graph class 𝒞 is said delineat...

0 Édouard Bonnet, et al. ∙

research

∙ 12/19/2021

Attacks of the Knights: Exploiting Non Uniform Cache Access Time

Intel Knights Landing Processors have shared last level cache (LLC) acro...

0 Farabi Mahmud, et al. ∙

research

∙ 11/05/2021

Directed flow-augmentation

We show a flow-augmentation algorithm in directed graphs: There exists a...

0 Eun Jung Kim, et al. ∙

research

∙ 10/30/2021

Twin-width VI: the lens of contraction sequences

A contraction sequence of a graph consists of iteratively merging two of...

0 Édouard Bonnet, et al. ∙

research

∙ 10/28/2021

EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs

A (unit) disk graph is the intersection graph of closed (unit) disks in ...

0 Marthe Bonamy, et al. ∙

research

∙ 07/06/2021

Twin-width and polynomial kernels

We study the existence of polynomial kernels, for parameterized problems...

0 Édouard Bonnet, et al. ∙

research

∙ 05/03/2021

A Constant-factor Approximation for Weighted Bond Cover

The Weighted ℱ-Vertex Deletion for a class F of graphs asks, weighted gr...

0 Eun Jung Kim, et al. ∙

research

∙ 04/28/2021

Continual Learning Approach for Improving the Data and Computation Mapping in Near-Memory Processing System

The resurgence of near-memory processing (NMP) with the advent of big da...

0 Pritam Majumder, et al. ∙

research

∙ 09/02/2020

Towards constant-factor approximation for chordal / distance-hereditary vertex deletion

For a family of graphs ℱ, Weighted ℱ-Deletion is the problem for which t...

0 Jungho Ahn, et al. ∙

research

∙ 08/17/2020

Grundy Distinguishes Treewidth from Pathwidth

Structural graph parameters, such as treewidth, pathwidth, and clique-wi...

0 Rémy Belmonte, et al. ∙

research

∙ 08/12/2020

On the tree-width of even-hole-free graphs

The class of all even-hole-free graphs has unbounded tree-width, as it c...

0 Pierre Aboulker, et al. ∙

research

∙ 07/28/2020

Twin-width III: Max Independent Set and Coloring

We recently introduced the graph invariant twin-width, and showed that f...

0 Édouard Bonnet, et al. ∙

research

∙ 07/17/2020

Solving hard cut problems via flow-augmentation

We present a new technique for designing FPT algorithms for graph cut pr...

0 Eun Jung Kim, et al. ∙

research

∙ 06/17/2020

Twin-width II: small classes

The twin-width of a graph G is the minimum integer d such that G has a d...

0 Édouard Bonnet, et al. ∙

research

∙ 04/30/2020

Twin-width I: tractable FO model checking

Inspired by a width invariant defined on permutations by Guillemot and M...

0 Édouard Bonnet, et al. ∙

research

∙ 01/11/2020

Grundy Coloring friends, Half-Graphs, Bicliques

The first-fit coloring is a heuristic that assigns to each vertex, arriv...

0 Pierre Aboulker, et al. ∙

research

∙ 10/10/2019

Remote Control: A Simple Deadlock Avoidance Scheme for Modular System on Chip

The increase in design cost and complexity have motivated designers to a...

0 Pritam Majumder, et al. ∙

research

∙ 02/13/2019

New Results on Directed Edge Dominating Set

We study a family of generalizations of Edge Dominating Set on directed ...

0 Rémy Belmonte, et al. ∙

research

∙ 11/30/2018

Spatial analysis between particulate matter and emergency room visits for conjunctivitis and keratitis

Background: The concentration of particulate matter in the air varies de...

0 Jung-Youb Le, et al. ∙

research

∙ 09/21/2018

Data-compression for Parametrized Counting Problems on Sparse graphs

We study the concept of compactor, which may be seen as a counting-analo...

0 Eun Jung Kim, et al. ∙

research

∙ 07/14/2018

Token Sliding on Split Graphs

We show that the independent set reconfiguration problem on split graphs...

0 Rémy Belmonte, et al. ∙

research

∙ 12/13/2017

QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs

A (unit) disk graph is the intersection graph of closed (unit) disks in ...

0 Édouard Bonnet, et al. ∙

research

∙ 11/04/2017

Finding branch-decompositions of matroids, hypergraphs, and more

Given n subspaces of a finite-dimensional vector space over a fixed fini...

0 Jisu Jeong, et al. ∙

research

∙ 11/02/2017

Erdős-Pósa property of chordless cycles and its applications

A chordless cycle in a graph G is an induced subgraph of G which is a cy...

0 Eun Jung Kim, et al. ∙

research

∙ 02/25/2014

The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation

We study the computational complexity of problems that arise in abstract...

0 Eun Jung Kim, et al. ∙

research

∙ 04/21/2011

Algorithms and Complexity Results for Persuasive Argumentation

The study of arguments as abstract entities and their interaction as int...

0 Eun Jung Kim, et al. ∙

Eun Jung Kim

Featured Co-authors