EUNJUNG KIM

Charge de Recherche CNRS (Junior Researcher)
Research team: Combinatorial Optimization, Algorithms, Data
Laboratory: LAMSADE

Contact

  • Phone: +33 (0)1 44 05 44 36
  • Email: eunjungkim78 at gmail.com
  • Address: Bureau P627, Place du Marechal de Lattre de Tassigny, 75775 Paris cedex 16, France
I did the master's degree at KAIST, South Korea and completed the PhD study in theoretical computer science at Royal Holloway, University of London in UK, 2010. I was a postdoc at Project Team ALGCo, CNRS-LIRMM in 2010-2011.

Research Interests

  • Fixed-Parameter Algorithms and lower bound
  • Constraint Satisfaction Problems
  • Graph Theory and structure, width parameters

Publications

  1. Jisu Jeong, Eun Jung Kim, Sang-il Oum, Constructive algorithm for path-width of matroids
    Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) arxiv

  2. E. J. Kim, Christophe Paul, Ignasi Sau and Dimitrios Thilikos,
    Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism
    Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) arxiv

  3. Holger Dell, E. J. Kim, Michael Lampis, Valia Mitsou and Tobias Momke
    Complexity and Approximability for Parameterized CSPs
    Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) arxiv

  4. E. J. Kim and O-Joung Kwon, A polynomial kernel for Block Graph Deletion
    Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). arxiv

  5. Mamadou Kante, E. J. Kim, O-Joung Kwon and Christophe Paul,
    An FPT algorithm and a polynomial kernel for Linear Rankwidth One Vertex Deletion
    Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). arxiv

  6. E. J. Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau and Dimitrios Thilikos,
    An FPT 2-Approximation for Tree-Cut Decomposition
    Proceedings of 13th Workshop on Approximation and Online Algorithms (WAOA 2015). arxiv

  7. Robert Ganian, E. J. Kim and Stefan Szeider, Algorithmic Applications of Tree-Cut Width
    Proceedings of the 40th Mathematical Foundations of Computer Science (MFCS 2015)

  8. E. J. Kim, Martin Milanic and Oliver Schaudt, Recognizing k-equistable graphs in FPT time
    Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015). arxiv

  9. Edouard Bonnet, Florent Foucaud, E. J. Kim, Florian Sikora, Complexity of Grundy coloring and its variants
    conference version: Proceedings of the 21st International Computing and Combinatorics Conference (COCOON 2015). arxiv

  10. N. Cohen, D. Goncalves, E. J. Kim, C. Paul, I. Sau, D. Thilikos, M. Weller,
    A Polynomial-time Algorithm for Outerplanar Diameter Improvement,
    conference version: Proceedings of the Proceedings of the 10th International Computer Science Symposium in Russia (CSR 2015). arxiv

  11. R. Crowston, M. Fellows, G. Gutin, M. Jones, E. J. Kim, F. Rosamond, I. Z. Ruzsa, S. Thomasse, A. Yeo,
    Satisfying More Than Half Linear Equations Over F2: A multivariate approach
    Journal of Computer and System Sciences. 80 (4), pp. 687-696, 2014. arxiv

  12. E. Bonnet, B. Escoffier, E. J. Kim, V. Paschos, On Subexponential and FPT-time Inapproximability,
    conference version: Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013). arxiv
    journal version: Algorithmica 71 (3), pp. 541-656, 2015.

  13. E. J. Kim, Sebastian Ordyniak, Stefan Szeider,
    The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation,
    Proceedings of the 2nd International Workshop on Theory and Applications of Formal Argumentation (TAFA 2013).

  14. E. J. Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, Somnath Sikdar,
    Linear kernels and single-exponential algorithms via protrusion decompositions,
    conference version: Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013). arxiv
    journal version: ACM Transactions on Algorithms (TALG) 12 (2), 2016.

  15. Daniel Goncalves, E. J. Kim, On Exact Algorithms for Permutation CSP
    Theoretical Computer Science. 511, pp. 109-116, 2013. arxiv

  16. E. J. Kim, Sebastian Ordyniak, Valued-Based Argumentation for Tree-like Value Graphs
    Proceedings of the 4th International Conference on Computational Models of Argument (COMMA 2012) pdf

  17. E. J. Kim, Christophe Paul, Geevarghese Philip, A single-exponential FPT algorithm for K4-minor cover problem
    conference version: Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012). arxiv
    journal version: Journal of Computer and System Sciences 81 (1), pp. 186-207, 2015.

  18. S. Gaspers, S. Szeider, S. Ordyniak, E.J. Kim, S. Saurabh, Don't Be Strict in Local Search!
    Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI-12). arxiv

  19. E. J. Kim, R. Williams, Improved Parameterized Algorithms for Above Average Constraint Satisfaction,
    Proceedings of the 6th International Symposium on Parameterized and Exact Computation (IPEC 2011). arxiv

  20. G. Gutin, E. J. Kim, M. Lampis, V. Mitsou, Vertex Cover Problem Parameterized Above and Below Tight Bounds,
    Theory of Computing Systems 48 (2), pp. 402-410, 2011. arxiv

  21. G. Gutin, E. J. Kim, A. Soleimanfallah, S. Szeider, A. Yeo, Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming,
    conference version: the 5th International Symposium on Parameterized and Exact Computation (IPEC 2010). pdf
    journal version: Algorithmica 64 (1), pp. 112-125, 2012.

  22. E. J. Kim, S. Ordyniak, S. Szeider, Complexity Results for Argumentation and Subjective Acceptance
    conference version: the 3rd International Conference on Computational Models of Argument (COMMA 2010).
    journal version: Artificial Intelligence 175 (9--10), pp. 1722-1736, 2011. arxiv

  23. G. Gutin, E. J. Kim, M. Mnich, A. Yeo, Betweenness Parameterized Above Tight Lower Bound,
    Journal of Computer and System Sciences 76 (8), pp. 872--878, 2010. arxiv

  24. R. Crowston, G. Gutin, M. Jones, E. J. Kim, I.Z. Ruzsa, Systems of Linear Equations over F_2 and Problems Parameterized Above Average
    Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010). arxiv

  25. N. Alon, G. Gutin, E. J. Kim, S. Szeider, A. Yeo, Solving Max r-SAT Above a Tight Lower Bound
    conference version: the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010).
    journal version: Algorithmica 61 (3), pp. 638-655, 2011. arxiv

  26. J. Daligault, G. Gutin, E. J. Kim, A. Yeo, FPT Algorithms and Kernels for the Directed k-Leaf Problem,
    Journal of Computer and System Sciences 76 (2), pp. 144-152, 2010. arxiv

  27. A. Gupta, G. Gutin, M. Karimi, E. J. Kim, A. Rafiey, Minimum Cost Homomorphisms to Locally Semicomplete and Quasi-transitive Digraphs
    Australasian Journal of Combinatorics 46, pp. 217-232, 2010. arxiv

  28. G. Gutin, E. J. Kim, The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops,
    Discrete Applied Mathematics 158 (4), pp. 319-330, 2010. arxiv

  29. G. Gutin, E. J. Kim, S. Szeider, A. Yeo, A Probabilistic Approach To Problems Parameterized Above Tight Lower Bound,
    conference version: Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC 2009). arxiv
    journal version: Journal of Computer and System Sciences 77 (2). pp. 422-429, 2011.

  30. N. Cohen, F. V. Fomin, G. Gutin, E. J. Kim, S. Saurabh, A. Yeo, Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem.
    conference version: Proceedings of the 15th International Computing and Combinatorics Conference (COCOON 2009). pdf
    journal version: Journal of Computer and System Sciences 76 (7), pp. 650-662, 2010.

  31. P. Dunkelmann, G. Gutin, E. J. Kim, On the Complexity of Minimum Leaf Out-branching Problem,
    Discrete Applied Mathematics
    157 (13), pp. 3000-3004, 2009. arxiv

  32. G. Gutin, E. J. Kim, I. Razgon, Minimum Leaf Out-branching and Related Problems,
    conference version: Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM 2008).
    journal version: Theoretical Computer Science 410 (45), pp. 4571-4579, 2009. arxiv

  33. A. Gupta, M. Karimi, E. J. Kim, A. Rafiey, Minimum Cost Homomorphisms to Locally In-semicomplete Digraphs,
    Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications (COCOA 2008). pdf

  34. G. Gutin, E. J. Kim, Properly Coloured Cycles and Paths: Results and Open Problems,
    LNCS Proceedings of the conference honoring Martin Golumbic's 60th birthday, 2008.

  35. G. Gutin, E. J. Kim, Introduction to the Minimum Cost Homomorphism Problem for Directed and Undirected Graphs,
    Lecture Notes of Ramanujan Mathematical Society 7, pp. 25-37, 2008. preprint-pdf

Thesis

  • PhD thesis: Parameterized Algorithms on Digraph and Constraint Satisfaction Problems (pdf) supervised by Gregory Gutin

Last update: 29 March 2016