LAMSADE
Kim Eun Jung
Chargé de recherche CNRS
Biographie
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 É., Kim E., Reinald A., Thomassé S., Watrigant R. (2022), Twin-width and Polynomial Kernels, Algorithmica, vol. 84, n°11, p. 3300-3337
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
Aboulker P., Adler I., Kim E., Sintiari N., Trotignon N. (2021), On the tree-width of even-hole-free graphs, European Journal of Combinatorics, vol. 98, p. 103394
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
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
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
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.
Gima T., Kim E., Khöler N., Melissinos N., Vasilakis M. (2023), Bandwidth Parameterized by Cluster Vertex Deletion Number, in Neeldhara Misra ; Magnus Wahlström, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 21:1-21:15 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 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., 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.
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.
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.
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.
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.
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.
Belmonte R., Hanaka T., Katsikarelis I., Kim E., Lampis M. (2018), New Results on Directed Edge Dominating Set, in Igor Potapov ; Paul Spirakis ; James Worrell, elsevier, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 67:1-67:16 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.
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.
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.
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.
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.
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.
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