Curriculum vitae

Kim Eun Jung

Chargé de recherche CNRS
LAMSADE

eun-jung.kimping@lamsade.dauphinepong.fr

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.

Dernières publications

Articles

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

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

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

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

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

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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

Retour à la liste