K.K's page Welcome to my homepage !!

Ken-ichi Kawarabayashi (Ph. D)

Professor, National Institute of Informatics and JST ERATO Kawarabayashi Project
E-mail: k_keniti_at_nii.ac.jp

NN_homepage

Research Interests:

Discrete Math and Theoretical Computer Science, AI, Graph Mining, Graph Data Base.

Curriculum Vitae:
 

Born in 1975 at Tokyo, Japan

Graduated from high school (Seiko Gakuin) in March 1994

Undergraduate Student at Keio University April 1994 - March 1998

Master Student at Keio University April 1998 - March 2000

Master's Degree 1999 from Keio University : title :Paths and Cycles in Graphs.

Doctor Student at Keio University April 2000 - March 2001

Ph.D. 2000 from Keio University : title : A Study on Hamiltonian Cycles and Related Topics.

Research Fellow of the Japan Society for the Promotion of Science, April 2000 - March 2003

Fujiwara Prize 2000 (for an outstanding graduate student in Keio University.)

Visiting Research Scholar at Vanderbilt University, April 2001- Aug 2002

Takebe Prize 2001 from Japanese Mathematics Society (for outstanding young Japanese mathematician.)

Research Fellow (Post Doc) at Princeton Univ. Aug 2002 - Aug 2003

Assistant Professor of Tohoku Univ. Aug 2003 -- March 2006.

Associate Professor of National Institute of Informatics, April 2006 -- October 2009.

Professor of National Institute of Informatics, November 2009--.

Inoue Research Award for Young Scientists 2003

Kirkman Prize 2003 from ICA (The Institute of Combinatorics and its Application.)

Research Fellowship from Sumitomo Foundation.

Visiting Professor of University of the Southern Denmark, July-October 2005.

JSPS research fellowship.

Research Fellowship from C&C Foundation

Research Fellowship for sabbatical 2007--2008 from the Japan Society for the Promotion of Science.

Young Researchers Prize from Ministry of Education, Culture, Sports, and Science and Technology , 2006 April.

Research Fellowship from Inamori Foundation, 2006.

Research Fellowship from Kayamori Foundation, 2007.

Best Paper from The 17th International Symposium on Algorithms and Computation (ISAAC 2006)

Japan IBM Science Prize in Computer Science, November, 2008.

Inoue Research Award, 2009, February.

Funai Research (special) Award,, 2011, March.

JST ERATO Kawarabayashi Project,, 2012 October -- 2018 March.

Click here for my CV.


 

Editorial Work:

  1. Siam Journal on Discrete Mathematics, Editor.
  2. Journal of Graph Theory, Editor.
  3. Discrete Mathematics and Theoretical Computer Science, Editor.
  4. International Journal of Combinatorics, Editor.

 

Program Committee:

  1. SODA11, Annual ACM-SIAM Symposium on Discrete Algorithms, 2011.
  2. Siam Discrete Math Conference, 2010.
  3. "New Trends on Structure Graph Theory" (with B. Mohar, B. Reed and P. Seymour), to be held at the Banff International Research Station, Sept. 5--10 in 2010.
  4. 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010), August, 2010.
  5. Kyoto Prize Satellite Workshop in Tokyo, November 16 - 18, 2010, Tokyo Tech Front, Tokyo Institute of Technology, Japan.
  6. 3rd Pacific Workshop on Discrete Mathematics, Dec. 7--10, 2010, Tokai University Pacific Center, Hawaii.
  7. Shonan meeting on Graph Algorithm and Combinatorial Optimization.
  8. Second Bertinoro workshop on Graphs and Algorithm, Bertinoro, 2011, Dec.
  9. SODA12, Annual ACM-SIAM Symposium on Discrete Algorithms, (I am on local program committee)2012.
  10. ESA'13(ALGO), European Symposium on Algorithms (ESA).
  11. TACM'13

 

Conference I plan to attend:

  1. EuroComb 2011, European Conference on Combinatorics, Graph Theory and Applications, Aug 29-Sep 2, Budapest, Hungary
  2. FOCS 2011 The 52nd Annual Symposium on Foundations of Computer Science (FOCS'11) at Hotel Zoso in Palm Springs, California, October 23-25.
  3. Second Bertinoro workshop on Graphs and Algorithm, Bertinoro, 2011, Dec. I am one of organizers.
  4. SODA12, Annual ACM-SIAM Symposium on Discrete Algorithms, 2012.
  5. Graph Theory at Georgia Tech (honoring Robin Thomas' 50th Birthday), May 7-11.
  6. Siam Discrete Math Conference, June 18-21, 2012 Dalhousie University, Halifax, Nova Scotia, Canada.
  7. Shonan meeting on Parameterized Complexity May, 2013.

 

KK's Published Papers here


 

Recent Papers

  1. The disjoint paths problem in quadratic time (with Y. Kobayashi and B. Reed), to appear in J. Combin. Theory Ser. B.
  2. On the excluded minor structure theorem for graphs of large treewidth (with R. Diestel, T. Muller and P. Wollan), to appear in J. Combin. Theory Ser. B.
  3. A Multi-Round Generalization of the Traveling Tournament Problem and its Application to Japanese Baseball (with R. Hoshino), to appear in European Journal of Operational Research.
  4. Connectivities for k-knitted graphs and for minimal counterexample to Hadwiger's Conjecture (with G. Yu), to appear in J. Combin. Theory Ser. B.
  5. An O(log n)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs (with Y. Kobayashi), to appear in ACM transaction on Algorithms.
  6. Packing Directed Circuits through Prescribed Vertices Bounded Fractionally (with N. Kakimura), to appear in Siam. J. Discrete Math.
  7. Linear min-max relation between the treewidth of $H$-minor-free graphs and its largest grid minor (with Y. Kobayashi), to appear in Symposium on Theoretical Aspects of Computer Science (STACS) 2012.
  8. Edge-disjoint Odd Cycles in $4$-edge-connected Graphs (with Y. Kobayashi), to appear in Symposium on Theoretical Aspects of Computer Science (STACS) 2012.
  9. Shortest-Path Queries for Complex Networks: Exploiting Low Tree-width Outside the Core, (with T. Akiba and C. Sommer) to appear in EDBT 2012 - 15th International Conference on Extending Database Technology.
  10. Fixed-parameter tractability for the subset feedback set problem and the $S$-cycle packing problem (Y. Kobayashi), to appear in J. Combin. Theory Ser. B.
  11. Packing Cycles through Prescribed Vertices under Modularity Constraints (with N. Kakimura), to appear in Advance in Applied Math.
  12. The Linear Distance Traveling Tournament Problem (with R. Hoshino), to appear in the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI-12).
  13. Removable paths and cycles with parity constraints (with O. Lee and B. Reed), to appear in J. Combin. Theory Ser. B.
  14. A simpler proof for the two disjoint odd cycles theorem (with K. Ozeki), to appear in J. Combin. Theory Ser. B.
  15. Generating Approximate Solutions to the Traveling Tournament Problem using a Linear Distance Relaxation (with R. Hoshino), to appear in Journal of Artificial Intelligence Research.
  16. Combinatorial coloring of 3-colorable graphs (with M. Thorup), to appear in 53rd Annual Symposium on Foundations of Computer Science (FOCS 2012).
  17. A Simple Algorithm for the Graph Minor Decomposition - Logic meets Structural Graph Theory (with M. Grohe and B. Reed), to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'13).
  18. 5-coloring $K_{3,k}$-minor-free graphs, to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'13).
  19. Totally odd subdivisions and parity subdivisions: Structures and Coloring, to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'13).
  20. Packing directed cycles through a specified vertex set (with M. Krcal, D. Kral and S. Kreutzer), to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'13).
  21. 4-connected projective planar graphs are hamiltonian-connected (with K. Ozeki), to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'13).
  22. More Compact Oracles for Approximate Distances in Undirected Planar Graphs (with C. Sommer and M. Thorup), to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'13).

 

News:

    JST ERATO Kawarabayashi Project,, 2012 October -- 2018 March.

  1. I am on the Local Committee of SODA12, Annual ACM-SIAM Symposium on Discrete Algorithms, 2012.
  2. Funai Research (special) Award,, 2011, March.
  3. Lovasz wins Kyoto prize 2010!
  4. SODA'12 will take place in Kyoto, Japan!
  5. As of Nov. 1, 2009, I am Professor of National Institute of Informatics.
  6. Inoue Research Award, 2009, February.
  7. Japan IBM Science Prize in Computer Science, November, 2008.
  8. I am on the Program Committee of SODA11, Annual ACM-SIAM Symposium on Discrete Algorithms, 2011.
  9. I am on the Program Committee of Siam Discrete Math Conference, 2010.
  10. I am co-organizing a workshop "New Trends on Structure Graph Theory" (with B. Mohar, B. Reed and P. Seymour), to be held at the Banff International Research Station, Sept. 5--10 in 2010.
  11. I am co-organizing a workshop "Bertinoro workshop on Graphs and Algorithm", Bertinoro, 2009, Dec.
  12. I am on the Program Committee of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010), August, 2010.
  13. Young Researchers Prize from Ministry of Education, Culture, Sports, and Science and Technology (Monka Syo) , 2006 April.
  14. Best Paper from The 17th International Symposium on Algorithms and Computation (ISAAC 2006).
  15. Winter School for Graphs and Algorithms. This is a part of project RIMS International Project Research 2008 Discrete Structures and Algorithms. I am an organizer. Carsten Thomassen, Bruce Reed, Bojan Mohar, Robin Thomas, Bjarne Toft, R. Ravi, S. Oum, M. Halldorsson, and Mikkel Thorup have agreed to give lectures.