Research Interests
- Graph theory, graph structure and width parameters
- Graph algorithms related with width parameters and fixed parameter tractable algorithms
Position
- Technische Universitat Berlin, Berlin, Germany (Jul. 2016 - )
- Postdoctor in Institut fur Softwaretechnik und Theoretische Informatik
- Advisor: Stephan Kreutzer
- Hungarian Academy of Sciences, Budapest, Hungary (Jul. 2015 - Jun. 2016)
- Researcher in Institute for Computer Science and Control (MTA SZTAKI)
- Advisor: Dániel Marx
Education
- Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Korea (Sep. 2012 - Aug. 2015)
- Ph.D. in Mathematical Science
- National Research Scholarship by the Korea Student Aid Foundation
- Advisor: Prof. Sang-il Oum
- Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Korea (Sep. 2010 - Aug. 2012)
- M.S. in Mathematical Science
- National Research Scholarship by the Korea Student Aid Foundation
- Advisor: Prof. Sang-il Oum
- Hanyang University, Seoul, Korea ( - Aug. 2010)
- B.S. in Mathmatics
- National Scholarship for Science and Engineering Students (KOSAF)
Submitted Manuscripts and Preprints
- 10. An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width (with Benjamin Bergougnoux and Mamadou Kanté)
- arXiv:1702.06095 submitted to conference
- 9. Neighborhood complexity and kernelization for nowhere dense classes of graphs
- (with Kord Eickmeyer, Archontia Giannopoulou, Stephan Kreutzer, Michal Pilipczuk, Roman Rabinovich, Sebastian Siebertz)
- arXiv:1612.08197 submitted to conference
- 8. Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
- (with Edouard Bonnet, Nick Brettell, and
Dániel Marx)
- submitted to conference
- 7. A polynomial kernel of Distance-Hereditary Vertex Deletion (with Eun Jung Kim)
- arXiv:1610.07229 submitted to conference
- 6. A width parameter useful for chordal and co-comparability graphs (with Dong Yeup Kang, Torstein Stromme, and Jan Arne Telle)
- arXiv:1606.08087 submitted 2016 (WALCOM 2017 accepted)
- 5. A single-exponential fixed-parameter algorithm for Distance-Hereditary Vertex Deletion
(with Eduard Eiben and Robert Ganian)
- arXiv:1604:06056 submitted 2016 (MFCS 2016 accepted)
- 4. Parameterized vertex deletion problems for hereditary graph classes with a block property (with Edouard Bonnet, Nick Brettell, and
Dániel Marx)
- arXiv:1603.05945 submitted 2016 (WG 2016 accepted)
- 3. Packing and covering immersion models of planar subcubic graphs (with Archontia Giannopoulou, Jean-Florent Raymond, and
Dimitrios M. Thilikos)
- arXiv:1602.04042 submitted 2016 (WG 2016 accepted)
- 2. A polynomial kernel for Block Graph Vertex Deletion (with Eun Jung Kim)
- arXiv:1506.08477 submitted 2015 (IPEC 2015 accepted)
- 1. Linear rank-width of distance-hereditary graphs II. Vertex-minor obstructions
(with Isolde Adler and Mamadou Kanté)
- arXiv:1508.04718 submitted 2015
Journal Papers
- 8. An FPT algorithm and a polynomial kernel for Linear Rankwidth-1 Vertex Deletion (with Mamadou Kanté, Eun Jung Kim, and Christophe Paul)
- 7. Linear rank-width of distance-hereditary graphs I. A polynomial time algorithm (with Isolde Adler and Mamadou Kanté)
- 6. Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors (with Ilkyoo Choi and Sang-il Oum)
- 5. Characterizing width two for variants of treewidth (with Hans L. Bodlaender, Stefan Kratsch, Vincent Kreuzen, and Seongmin Ok)
- 4. Tree-depth and vertex-minors (with Pétr Hlineny, Jan Obdrzalek, and Sebastian Ordyniak)
- 3. Excluded vertex-minors for graphs of linear rank-width k (with Jisu Jeong and Sang-il Oum)
- 2. Unavoidable vertex-minors in large prime graphs (with Sang-il Oum)
- 1. Graphs of small rank-width are pivot-minors of graphs of small tree-width (with Sang-il Oum)
Thesis
- Ph.D. Thesis
- On the structural and algorithmic properties of linear rank-width [File]
- Master Thesis
- Connecting rank-width and tree-width via pivot-minors [File]
Refereed Conference Papers
- 8. A width parameter useful for chordal and co-comparability graphs (with Dong Yeup Kang, Torstein Stromme, and Jan Arne Telle)
- WALCOM 2017 accepted
- 7. A single-exponential fixed-parameter algorithm for Distance-Hereditary Vertex Deletion (with Eduard Eiben and Robert Ganian)
- MFCS 2016, DOI: 10.4230/LIPIcs.MFCS.2016.34
- 6. Packing and covering immersion models of planar subcubic graphs (with Archontia Giannopoulou, Jean-Florent Raymond, and
Dimitrios M. Thilikos)
- WG 2016, DOI: 10.1007/978-3-662-53536-3_7
- 5. Parameterized vertex deletion problems for hereditary graph classes with a block property (with Edouard Bonnet, Nick Brettell, and
Dániel Marx)
- WG 2016, DOI: 10.1007/978-3-662-53536-3_20
- 4. A polynomial kernel for Block Graph Vertex Deletion (with Eun Jung Kim)
- IPEC 2015, DOI:10.4230/LIPIcs.IPEC.2015.270
- 3. FPT algorithm and polynomial kernel for linear rank-width one vertex deletion (with Mamadou Kanté, Eun Jung Kim, and Christophe Paul)
- IPEC 2015, DOI:10.4230/LIPIcs.IPEC.2015.138
- 2. Linear rank-width of distance-hereditary graphs (with Isolde Adler and Mamadou Kanté)
- WG 2014, DOI: 10.1007/978-3-319-12340-0_4
- 1. Excluded vertex-minors for graphs of linear rank-width k (with Jisu Jeong and Sang-il Oum)
- STACS 2013, DOI: 10.4230/LIPIcs.STACS.2013.221
Research Project
- Unavoidable vertex-minors for linear rank-width at most k
- Kernel for rank-width deletion problem, general rank-width protrusion concepts, ..
- A generalization of Mader's S-path theorem and applications
- Properties of Matroid path-width
- Properties of H-pivot-minor / H-vertex-minor graphs
Grants
- RWTH Aachen University Research Fellowship Korea, Jan - Mar, 2015
- KIAS Fellowship for Seoul ICM 2014
- SIAM Student Travel Award - SIAM Conference on Discrete Mathematics, June, 2014
- Travel Grants for graduate students and young researchers - 14th Max Planck Advanced Course on the Foundations of Computer Science, Aug, 2013
Research Visitings
- Universidad Politecnica de Valencia, Valencia, Spain (27. Mar. 2017 ~ 1. Apr. 2017)
- Durham University, Durham, UK (27. Feb. 2017 ~ 3. Mar. 2017)
- University of Warsaw, Warsaw, Poland (11. Jan. 2017 ~ 13. Jan. 2017)
- KAIST, South Korea (20. Nov. 2016 ~ 10. Nov. 2016)
- Universite Blaise Pascal in Clermont-ferrand, France (7. Nov. 2016 ~ 12. Nov. 2016)
- University of Bergen in Bergen, Norway (22. May. 2016 ~ 28. May. 2016)
- TU Wien in Vienna, Austria (14. Mar. 2016 ~ 18. Mar. 2016)
- Masaryk University in Brno, Czech (16. Nov. 2015 ~ 20. Nov. 2015)
- MTA SZTAKI in Budapest, Hungary (22. Mar, 2015 ~ 28. Mar, 2015)
- DTU in Lyngby, Denmark (23. Feb, 2015 ~ 27. Feb, 2015)
- Bonn University, Germany (16. Feb, 2015 ~ 18. Feb, 2015)
- LIRMM in Montpellier, France (26. Jan, 2015 ~ 30. Jan, 2015)
- RWTH Aachen University in Aachen, Germany (6. Jan, 2015 ~ 31. Mar, 2015)
- Universite Blaise Pascal in Clermont-ferrand, France (7. July. 2014 ~ 22. July. 2014)
- Utrecht University in Utrecht, Netherlands (15. Feb. 2014 ~ 7. Mar. 2014)
- Universite Blaise Pascal in Clermont-ferrand, France (8. July. 2013 ~ 21. July. 2013)
- Masaryk University in Brno, Czech (19. May. 2013 ~ 24. May. 2013)
- University of Hamburg in Hamburg, Germany (13. Feb. 2013 ~ 31. Aug. 2013)
Teaching Experiences
- Teaching assistance : Introduction to Graph Theory (MAS477) , Fall 2014
- Teaching assistance : Discrete Math (MAS255) , Spring 2014
- Teaching assistance : Introduction to Graph Theory (MAS477) , Fall 2012
- Teaching assistance : Discrete Math (MAS255) , Spring 2012
- Teaching assistance : Introduction to Graph Theory (MAS477) , Fall 2011
- Teaching assistance : Discrete Math (MAS255) , Spring 2011
Presentations
- Seminar at University of Warsaw, Warsay, Polland, 12 Jan, 2017.
- 14th KIAS Combinatorics Workshop Series at Busan, 19 Dec, 2016.
- 80th KPPY Combinatorics Workshop at Yeungnam Univ, Daegu, 17 Dec, 2016.
- Discrete Math Seminar at KAIST, 25 Nov, 2016.
- Colloquium talk on Methods for Discrete Structures in TU Berlin, Berlin, Germany, 24 Oct, 2016.
- SIWAG 2016 , Italy, 26 Sep, 2016.
- Coloring graphs without fan vertex-minors and cycle pivot-minors [Presentation file]
- MFCS 2016 , Krakow, Polland, 22 Aug, 2016.
- Seminar at University of Bergen, Bergen, Norway, 27 May, 2016.
- Seminar at MTA SZTAKI, Budapest, Hungary, 5 May, 2016.
- A single-exponential fixed parameter algorithm for Distance-Hereditary Vertex Deletion [Presentation file]
- Seminar at TU Wien in Vienna, Austria, 14. Mar, 2016.
- Seminar at Masaryk University in Brno, Czech, 16 Nov, 2015.
- Seminar at MTA SZTAKI, Budapest, Hungary, 28 Oct, 2015.
- 7th workshop on Graph Classes, Optimization, and Width Parameters, Aussois, France, 12 Oct, 2015.
- Erdos-Posa property of planar-H-minor models with prescribed vertex sets
- 10th International Symposium on Parameterized and Exact Computation, Patras, Greece, 17 Sep, 2015.
- A polynomial kernel for Block Graph Deletion [Presentation file]
- 10th International Symposium on Parameterized and Exact Computation, Patras, Greece, 16 Sep, 2015.
- An FPT algorithm and a polynomial kernel for linear rank-width one vertex deletion [Presentation file]
- Seminar at MTA SZTAKI, Budapest, Hungary , 29 Jul, 2015.
- Seminar at Korea University, Korea University, Seoul, Korea , 29 May, 2015.
- 2015 spring annual meeting of the KMS, Busan National University, Busan, Korea , 25 Apr, 2015.
- Siminar at KAIST, Daejeon, Korea , 15 Apr, 2015.
- Siminar at Bonn University, Bonn, Germany , 18 Feb, 2015.
- LIRMM Seminar, Montpellier, France , 22 Jan, 2015.
- International Workshop on Graph Decomposition, CIRM, Marseille, France , 22 Jan, 2015.
- KAIST Discrete Math Seminar , KAIST, Daejeon, Korea, 2 December, 2014.
- 66th KPPY Combinatorics Workshop , Yeungnam University, Daegu, Korea, 20 September, 2014.
- International Congress of Mathematicians, Seoul, Korea, 13-21 Augest, 2014.
- 9th International colloquium on graph theory and combinatorics, University Joseph Fourier, Grenoble, France, 30 June, 2014.
- 40th International Workshop on Graph-Theoretic Concepts in Computer Science, Le Domaine de Chales, near Orleans, France, 25-27 June, 2014.
- Linear rank-width of distance-hereditary graphs
- 2014 SIAM Discrete Math Conference, Hyatt Regency Minneapolis Minneapolis, Minnesota, USA, 18 June, 2014.
- The 4th KIAS Combinatorics Workshop, KIAS, Seoul, Korea , 30 May, 2014.
- 2014 spring annual meeting of the KMS, Wonju University, Gangneung, Korea , 25 Apr, 2014.
- 6th Workshop on GRAph Searching, Theory and Applications, Institut d'Etudes Scientifiques of Cargese, Corsica, France , 31 Mar 2014
- Seminar at Utrecht University in Utrecht, Utrecht University, Utrecht, Netherlands , 28 Feb 2014
- Dagstuhl seminar on Graph Modification Problems, Wadern, Germany 14 Feb 2014,
- Characterizing width two for variants of treewidth
- 12th Korea-Japan Workshop on Algebra and Combinatorics, KAIST, Daejeon , 23 Jan, 2014.
- Seminar at Hanyang University, Seoul , 29 Nov, 2013.
- Seminar at National Institute of Mathematical Sciences, Daejeon , 28 Nov, 2013.
- Kernelization in combinatorial optimization problems and the hierarchy of series-parallel graphs
- KPPY Combinatorics Workshop , Kyungbook University, Daegu , 9 Nov, 2013.
- Tree-like structure of distance-hereditary graphs
- 2013 annual meeting of the KMS, University of Seoul, Seoul , 25 Oct, 2013.
- Discrete Seminar at KAIST, Daejeon , 4 Oct, 2013.
- Unavoidable vertex-minors in large prime graphs [Presentation file]
- Visiting at University of Hamburg in Hamburg, Germany , 5 June, 2013.
- Unavoidable vertex-minors in large prime graphs
- Working Seminar on Formal Models, Discrete Structures, and Algorithms at Masaryk University in Brno, Czech , 20 May, 2013
- The 30th Symposium on Theoretical Aspects of Computer Science , Christian-Albrechts-Universitat zu Kiel, Kiel, Germany , 28 Feb, 2013.
- Excluded vertex-minors for graphs of linear rank-width at most k
- 2012 annual meeting of the KMS, Convention Center, Daejeon, 6 Oct, 2012.
- Seminar for graduate students in KAIST, Daejeon, 1 May, 2012.
- 2012 SIAM Discrete Math Conference, Dalhousie University, Halifax, Canada, 22 June, 2012.
- Graphs of small rank-width are pivot-minors of graphs of small tree-width [Presentation file]
- 5th workshop on Graph Classes, Optimization, and Width parameters, KAIST, Daejeon, 30 Oct, 2011.
- Pivot-minors and Vertex-minors of trees and paths