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

Ken-ichi Kawarabayashi (Ph. D)

Professor, National Institute of Informatics
E-mail: k_keniti_at_nii.ac.jp

NN_homepage

Research Interests:

Discrete Math and Theoretical Computer Science. More precisely, Graph theory, Combinatorics and Algorithm, in particular, Paths, Cycles, Connectivity, Factor, Coloring, Subdivisions, Minors, Surfaces, Hadwiger's Conjecture, Linkage Problem, Planar graphs, Graphs on Surfaces, and Perfect graphs and its application. Also Graph Algorithm and Combinatorial Optimization and Approximation algorithm for NP-hard problems.

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.

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.

 

Conference I plan to attend:

  1. Kyoto Prize Satellite Workshop in Tokyo, November 16 - 18, 2010, Tokyo Tech Front, Tokyo Institute of Technology, Japan. I am one of organizers.
  2. Shonan meeting on Graph Algorithm and Combinatorial Optimization, Shonan, Feb. 13-18, 2011. I am one of organizers.
  3. WALCOM, Workshop on Algorithm and Computation, in New Delhi, India on February 18-20, 2011.
  4. Graph Theory 2011, Hotel Koldingfjord in Kolding, Denmark, April 28 - May 1,
  5. The 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, RIMS, Kyoto, May 31--June 2.
  6. The 43rd ACM Symposium on Theory of Computing (STOC 2011), San Jose, CA, June 6 - June 8.
  7. The Twenty-Fifth Conference on Artificial Intelligence (AAAI-11), San Francisco, California at the Hyatt Regency San Francisco, August 7-11, 2011
  8. EuroComb 2011, European Conference on Combinatorics, Graph Theory and Applications, Aug 29-Sep 2, Budapest, Hungary
  9. FOCS 2011 The 52nd Annual Symposium on Foundations of Computer Science (FOCS'11) at Hotel Zoso in Palm Springs, California, October 23-25.
  10. Second Bertinoro workshop on Graphs and Algorithm, Bertinoro, 2011, Dec. I am one of organizers.
  11. SODA12, Annual ACM-SIAM Symposium on Discrete Algorithms, 2012.
  12. Siam Discrete Math Conference, June 18-21, 2012 Dalhousie University, Halifax, Nova Scotia, Canada.

 

KK's Published Papers here


 

Papers to appear.

  1. From the plane to higher surfaces, (with C. Thomassen), to appear in J. Combin. Theory Ser. B.
  2. Three-coloring triangle-free planar graphs in linear time (with Z. Dvorak and R. Thomas), to appear in ACM transaction on Algorithms.
  3. Minors in 5-connected non-planar large graphs (with J. Maharry), to appear in J. Graph Theory.
  4. The disjoint paths problem in quadratic time (with Y. Kobayashi and B. Reed), to appear in J. Combin. Theory Ser. B.
  5. The Erdos-Posa property for clique minors in highly connected graphs (with R. Diestel and P. Wollan), to appear in J. Combin. Theory Ser. B.
  6. 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.
  7. The Multi-Round Balanced Traveling Tournament Problem (with R. Hoshino), to appear in the 21st International Conference on Automated Planning and Scheduling (ICAPS'11).
  8. Contraction Decomposition in H-Minor-Free Graphs and Algorithmic Applications (with E. Demaine and M. Hajiaghayi), to appear in 43rd ACM Symposium on Theory of Computing (STOC'11).
  9. A simpler algorithm and shorter proof for the graph minor decomposition (with P. Wollan), to appear in 43rd ACM Symposium on Theory of Computing (STOC'11).
  10. Finding topological subgraphs is fixed-parameter tractable (with M. Grohe, D. Marx and P.Wollan), to appear in 43rd ACM Symposium on Theory of Computing (STOC'11).
  11. Breaking $O(n^{1/2})$-approximation algorithms for the edge-disjoint paths problem (with Y. Kobayashi), to appear in 43rd ACM Symposium on Theory of Computing (STOC'11).
  12. The Inter-League Extension of the Traveling Tournament Problem and its Application to Sports Schedule (with R. Hoshino), to appear in the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI-11).
  13. 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.
  14. Improved Algorithm for the Half-Disjoint Paths Problem (with Y. Kobayashi), to appear in Siam J. Discrete Math.
  15. Linkless and flat embeddings in 3-space (with S. Kreutzer and B. Mohar), to appear in Discrete and Computational Geometry.
  16. Connectivities for k-knitted graphs and for minimal counterexample to Hadwiger's Conjecture (with G. Yu), to appear in J. Combin. Theory Ser. B.
  17. The minimum k-way cut of bounded size is fixed-parameter tractable (with M. Thorup), to appear in the 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011).
  18. The Graph Minor Algorithm with Parity Conditions (with B. Reed and P. Wollan), to appear in the 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011).
  19. 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.
  20. Scheduling Bipartite Tournaments to Minimize Total Travel Distance (with R. Hoshino), Journal of Artificial Intelligence Research, 41 (2011), 527--561.
  21. Spanning closed walks and TSP in 3-connected planar graphs (with K. Ozeki), to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'12).
  22. Erd\H{o}s-P\'osa property and its algorithmic applications --- parity constraints, subset feedback set, and subset packing (with N. Kakimura and Y. Kobayashi), to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'12).
  23. List-Coloring Graphs without Subdivisions and without Immersions (with Y. Kobayashi, to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'12).
  24. A Linear Time Algorithm for the Induced Disjoint Paths Problem in Planar Graphs (with Y. Kobayashi), to appear in Journal of Computer and System Sciences.

 

News:

  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.