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 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
  • Linear matroids and algorithmic applications

Publications

  1. Eun Jung Kim, Maria Serna, Dimitrios M. Thilikos,
    Data-compression for Parametrized Counting Problems on Sparse graphs
    conference version: to appear in the proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018)

  2. Robert Ganian, Eun Jung Kim, Friedrich Slivovsky, Stefan Szeider,
    Weighted Counting for Constraint Satisfaction with Default Values: Algorithms and Complexity Results
    conference version: to appear in the proceedings of the 30th International Conference on Tools with Artificial Intelligence (ICTAI 2018)

  3. Remy Belmonte, Tesshu Hanaka, Ionnis Katsikarelis, Eun Jung Kim, Michael Lampis,
    New Results on Directed Edge Dominating Set
    conference version: to appear in the proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

  4. Jisu Jeong, Eun Jung Kim, Sang-il Oum, Finding branch-decompositions of matroids, hypergraphs, and more
    conference version: proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP 2018) arxiv

  5. Edouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Pawel Rzcazewski and Florian Sikora
    QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs
    conference version: Proceedings of the International Symposium on Computational Geometry (SoCG 2018) arxiv

  6. E. J. Kim and O-Joung Kwon, Erdos-Posa property of chordless cycles and its applications
    conference version: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2018) arxiv

  7. Eun Jung Kim, O-joung Kwon, A Polynomial Kernel for Distance-Hereditary Vertex Deletion
    conference version: Proceedings of the Workshop on Algorithms and Data Structures (WADS 2017) arxiv
    journal version: Algorithmica 79(1): 66-95 (2017)

  8. Jisu Jeong, Eun Jung Kim, Sang-il Oum, Constructive algorithm for path-width of matroids
    conference version: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2016) arxiv
    journal version: IEEE Trans. Information Theory 63(11): 7178-7205 (2017)

  9. E. J. Kim, Christophe Paul, Ignasi Sau and Dimitrios Thilikos,
    Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism
    conference version: Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) arxiv
    journal version: Comput. Syst. Sci. 86: 191-206 (2017)

  10. Holger Dell, E. J. Kim, Michael Lampis, Valia Mitsou and Tobias Momke
    Complexity and Approximability for Parameterized CSPs
    conference version: Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) arxiv
    journal version: Algorithmica 79(1): 230-250 (2017)

  11. E. J. Kim and O-Joung Kwon, A polynomial kernel for Block Graph Deletion
    conference version: Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). arxiv
    journal version: Algorithmica 79(1): 251-270 (2017)

  12. Mamadou Kante, E. J. Kim, O-Joung Kwon and Christophe Paul,
    An FPT algorithm and a polynomial kernel for Linear Rankwidth One Vertex Deletion
    conference version: Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). arxiv
    journal version: Algorithmica 79(1): 66-95 (2017)

  13. E. J. Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau and Dimitrios Thilikos,
    An FPT 2-Approximation for Tree-Cut Decomposition
    conference version: Proceedings of 13th Workshop on Approximation and Online Algorithms (WAOA 2015). arxiv
    journal version: Algorithmica 80 (1): 116--135 (2018)

  14. 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)

  15. 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

  16. 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
    journal version: Discrete Applied Mathematics 2018.

  17. 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
    journal version: J. Comput. Syst. Sci. 89: 315-327 (2017)

  18. 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

  19. 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.

  20. 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).

  21. 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.

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

  23. 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

  24. 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.

  25. 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

  26. 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

  27. 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

  28. 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.

  29. 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

  30. 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

  31. 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

  32. 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

  33. 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

  34. 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

  35. 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

  36. 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.

  37. 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.

  38. 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

  39. 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

  40. 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

  41. 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.

  42. 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: 23 May 2018