Kim Eun Jung - CV

LAMSADE

Kim Eun Jung

CNRS Researcher

Biography

Eun Jung Kim did a master's degree at KAIST, South Korea, before completing her PhD study in computer science at Royal Holloway, University of London in the UK. She works in particular on fixed-parameter algorithms, constraint satisfaction problems, linear matroids and their algorithmic applications.

Publications

Articles

Kanté M., Kim E., Kwon O-J., Oum S-I. (2023), Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k, Journal of Combinatorial Theory. Series B, vol. 160, p. 15-35

Aboulker P., Bonnet É., Kim E., Sikora F. (2023), Grundy Coloring and Friends, Half-Graphs, Bicliques, Algorithmica, vol. 85, n°1, p. 1-28

Belmonte R., Hanaka T., Katsikarelis I., Kim E., Lampis M. (2023), New Results on Directed Edge Dominating Set, Discrete Mathematics and Theoretical Computer Science, vol. vol. 25:1

Ahn J., Kim E., Lee E. (2022), Towards Constant-Factor Approximation for Chordal/Distance-Hereditary Vertex Deletion, Algorithmica, vol. 84, n°7, p. 2106-2133

Belmonte R., Kim E., Lampis M., Mitsou V., Otachi Y. (2022), Grundy Distinguishes Treewidth from Pathwidth, SIAM Journal on Discrete Mathematics, vol. 36, n°3, p. 1761-1787

Bonnet É., Geniet C., Kim E., Thomassé S., Watrigant R. (2022), Twin-width II: small classes, Combinatorial Theory, vol. 2, n°2

Kim E., Milanic M., Monnot J., Picouleau C. (2022), Complexity and algorithms for constant diameter augmentation problems, Theoretical Computer Science, vol. 904, p. 15-26

Sikora F., Belmonte R., Kim E., Lampis M., Mitsou V., Otachi Y. (2021), Token Sliding on Split Graphs, Theory of Computing Systems, vol. 65, n°4, p. 662–686

Bonamy M., Bonnet E., Bousquet N., Charbit P., Giannopoulos P., Kim E., Rzążewski P., Sikora F., Thomassé S. (2021), EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs, Journal of the ACM (JACM), vol. 68, n°2, p. 1–38

Bonnet É., Kim E., Thomassé S., Watrigant R. (2021), Twin-width I: tractable FO model checking, Journal of the ACM (JACM), vol. 69, n°1, p. 1–46

Jeong J., Kim E., Oum S-I. (2021), Finding Branch-Decompositions of Matroids, Hypergraphs, and More, SIAM Journal on Discrete Mathematics, vol. 35, n°4, p. 2544-2617

Kim E., Kwon O-J. (2020), Erdős-Pósa property of chordless cycles and its applications, Journal of Combinatorial Theory. Series B, vol. 145, p. 65-112

Bonnet E., Foucaud F., Kim E., Sikora F. (2018), Complexity of Grundy coloring and its variants, Discrete Applied Mathematics, vol. 243, p. 99-114

Kim E., Oum S-i., Paul C., Sau I., Thilikos D. (2018), An FPT 2-Approximation for Tree-Cut Decomposition, Algorithmica, vol. 80, n°1, p. 116-135

Jeong J., Kim E., Oum S-I. (2017), The “Art of Trellis Decoding” Is Fixed-Parameter Tractable, IEEE Transactions on Information Theory, vol. 63, n°11, p. 7178-7205

Dell H., Kim E., Lampis M., Mitsou V., Mömke T. (2017), Complexity and Approximability of Parameterized MAX-CSPs, Algorithmica, vol. 79, n°1, p. 230-250

Paschos V., Kim E., Bonnet E., Escoffier B. (2015), On Subexponential and FPT-Time Inapproximability, Algorithmica, vol. 71, n°3, p. 541-565

Kim E., Philip G., Paul C. (2015), A single-exponential FPT algorithm for the K4-minor cover problem, Journal of Computer and System Sciences, vol. 81, n°1, p. 186-207

Yeo A., Crowston R., Kim E., Thomassé S., Ruzsa I., Rosamond F., Jones M., Gutin G., Fellows M. (2014), Satisfying more than half of a system of linear equations over GF(2): A multivariate approach, Journal of Computer and System Sciences, vol. 80, n°4, p. 687-696

Kim E., Gonçalves D. (2013), On Exact Algorithms for Permutation CSP, Theoretical Computer Science, vol. 511, p. 109-116

Kim E., Yeo A., Szeider S., Soleimanfallah A., Gutin G. (2012), Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming, Algorithmica, vol. 64, n°1, p. 112-125

Chapitres d'ouvrage

Ordyniak S., Kim E. (2012), Valued-Based Argumentation for Tree-like Value Graphs, in Woltran, Stefan, Computational Models of Argument IOS Press, p. 378-389

Communications avec actes

Kim E., Kratsch S., Pilipczuk M., Wahlström M. (2023), Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints, in Nikhil Bansal ; Viswanath Nagarajan, elsevier, Philadelphia, SIAM - Society for Industrial and Applied Mathematics, 3218-3228 p.

Kim E., Kratsch S., Pilipczuk M., Wahlström M. (2022), Directed flow-augmentation, in Stefano Leonardi ; Anupam Gupta, elsevier, New York, NY, ACM - Association for Computing Machinery, 938-947 p.

Bonnet E., Chakraborty D., Kim E., Kohler N., Teixeira Lopes R., Thomassé S. (2022), Twin-width VIII: delineation and win-wins, in Holger Dell; Jesper Nederlof, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 520 p.

Bonnet E., Geniet C., Kim E., Thomassé S., Watrigant R. (2021), Twin-width II: small classes, in , alexandria, New York, NY, ACM - Association for Computing Machinery, 1977–1996 p.

Kim E., Lee E., Thilikos D. (2021), A Constant-Factor Approximation for Weighted Bond Cover, in Mary Wootters, Laura Sanità, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 7:1--7:14 p.

Bonnet E., Kim E., Reinald A., Thomassé S., Watrigant R. (2021), Twin-width and polynomial kernels, in Petr A. Golovach, Meirav Zehavi, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 6:1-6:13 p.

Kim E., Kratsch S., Pilipczuk M., Wahlström M. (2021), Solving hard cut problems via flow-augmentation, in Marx, Dániel, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 149-168 p.

Bonnet E., Geniet C., Kim E., Thomassé S., Watrigant R. (2021), Twin-width III: Max Independent Set, Min Dominating Set, and Coloring, in Bansal, Nikhil; Merelli, Emanuela; Worrell, James, Glasgow, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 35:1--35:20 p.

Bonnet E., Kim E., Thomassé S., Watrigant R. (2020), Twin-width I: tractable FO model checking, in , 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 601-612 p.

Belmonte R., Kim E., Lampis M., Mitsou V., Otachi Y. (2020), Grundy Distinguishes Treewidth from Pathwidth, in Public, John Q.; Access, Joan R., Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 23:1–23:27 p.

Ahn J., Kim E., Lee E. (2020), Towards constant-factor approximation for chordal / distance-hereditary vertex deletion, in Cao, Yixin; Cheng, Siu-Wing; Li, Minming, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 62:1–62:16 p.

Aboulker P., Bonnet E., Kim E., Sikora F. (2020), Grundy Coloring & Friends, Half-Graphs, Bicliques, in , 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 58:1-58:18 p.

Belmonte R., Kim E., Lampis M., Mitsou V., Otachi Y., Sikora F. (2019), Token Sliding on Split Graphs, in Rolf Niedermeier, Christophe Paul, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 13:1--13:17 p.

Ganian R., Kim E., Slivovsky F., Szeider S. (2018), Sum-of-Products with Default Values: Algorithms and Complexity Results, in , Piscataway, NJ, IEEE - Institute of Electrical and Electronics Engineers, 733-737 p.

Bonnet E., Giannopoulos P., Kim E., Rzazewski P., Sikora F. (2018), QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs, in Bettina Speckmann, Csaba D. Tóth, 34th International Symposium on Computational Geometry (SoCG 2018), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 12:1-12:15 p.

Kim E., Kwon O-j. (2018), Erdős-Pósa property of chordless cycles and its applications, in Artur Czumaj, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 1665-1684 p.

Jeong J., Kim E., Oum S-i. (2016), Constructive algorithm for path-width of matroids, in Robert Krauthgamer, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 1695-1704 p.

Dell H., Kim E., Lampis M., Mitsou V., Mömke T. (2015), Complexity and Approximability of Parameterized MAX-CSPs, in Thore Husfeldt, Iyad Kanj, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), Patras, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 294-306 p.

Bonnet E., Foucaud F., Kim E., Sikora F. (2015), Complexity of Grundy Coloring and Its Variants, in Dachuan Xu, Donglei Du, Dingzhu Du, Computing and Combinatorics. 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings, Springer, 109-120 p.

Paul C., Kim E., Kanté M., Kwon O-j. (2015), An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion, in , IPEC: International symposium on Parameterized and Exact Computation, Sep 2015, Patras, Greece, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 139-150 p.

Kim E., Ordyniak S., Szeider S. (2014), The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation, in Elizabeth Black, Sanjay Modgil, Nir Oren, Theory and Applications of Formal Argumentation; Second International Workshop, TAFA 2013, Beijing, China, August 3-5, 2013, Revised Selected papers, Springer, 158-175 p.

Kim E., Langer A., Paul C., Reidl F., Rossmanith P., Sau I., Sikdar S. (2013), Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions, in Fedor V. Fomin, Rūsiņš Freivalds, Marta Kwiatkowska, David Peleg, Automata, Languages, and Programming. 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, Springer, 613-624 p.

Kim E., Williams R. (2012), Improved Parameterized Algorithms for above Average Constraint Satisfaction, in Rossmanith, Peter, Parameterized and Exact Computation 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers, Saarbrücken, Springer, 273 p.

Ordyniak S., Kim E., Gaspers 0., Saurabh S., Szeider S. (2012), Don't Be Strict in Local Search!, in Selman, Bart, Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, Toronto, AAAI Press, 10 p.

Communications sans actes

Bonnet E., Kim E., Reinald A., Thomassé S. (2022), Twin-width VI: the lens of contraction sequences, ACM-SIAM Symposium on Discrete Algorithms (SODA22), Alexandria, États-Unis

Prépublications / Cahiers de recherche

Bonnet É., Chakraborty D., Kim E., KOHLER N., Lopes R., Thomassé S. (2023), Twin-width VIII: delineation and win-wins, Paris, Preprint Lamsade

Aboulker P., Adler I., Kim E., Sintiari N., Trotignon N. (2021), On the tree-width of even-hole-free graphs, Paris, Preprint Lamsade

Back to the list