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

Click here for my CV.


 

Editorial Work:

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

 

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

 

Conference I plan to attend:

  1. 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.
  2. Fourth workshop on Graph Classes, Optimization, and Width Parameters - GROW 2009 Bergen, Norway, October 15-17, 2009
  3. The 50th Annual Symposium on Foundations of Computer Science ( FOCS 2009) , October 24-27, in Atlanta, Georgia, USA. I will speak.
  4. Danish Graph Theory 2009, the conference center Trinity in Fredericia, Denmark, Nov. 26-29, 2009.
  5. Bertinoro workshop on Graphs and Algorithm, Bertinoro, 2009, Dec. I am one of organizers.
  6. SODA10, Annual ACM-SIAM Symposium on Discrete Algorithms in Austin. I will speak.
  7. Graph Theory, Oberwolfach, 2010, Feb.
  8. The 42th ACM Symposium on Theory of Computing (STOC 2010), Cambridge, MA, June 6 - June 8. I will speak.
  9. Siam Discrete Math Conference, 2010. June, 2010, Austin. I am on the Program Committee.
  10. International Conference on Recent Trends in Graph theory and Combinatorics, Aug 12-15, Cochin, India
  11. New trends in structural graph theory, Banff International Research Station, September 5-10, 2010. I am one of the organizers.
  12. SODA11, Annual ACM-SIAM Symposium on Discrete Algorithms in San Francisco. I am on the Program Committee.

 

KK's Published Papers here


 

Papers to appear.

  1. Degree Sum Conditions and Graphs Which are not Covered by k Cycles, to appear in Discrete Math.
  2. Acyclic coloring and Star coloring surfaces (with B. Mohar), to appear in Siam J. Discrete Math.
  3. Approximating the list-chromatic number of minor-closed class of graphs (with B. Mohar), to appear in Theoretical Computer Science.
  4. Linear connectivity forces large complete bipartite minors (with T. Bohme, J. Maharry and B. Mohar), to appear in J. Combin. Theory Ser B.
  5. Contractible triples in highly connected graphs (with S. Fujita), to appear in Annals of Combinatorics.
  6. From the plane to higher surfaces, (with C. Thomassen), to appear in J. Combin. Theory Ser. B.
  7. Dominating sets in triangulations on surfaces (with T. Honjo and A. Nakamoto), to appear in J. Graph Theory.
  8. Contractible small subgraphs in $k$-connected graphs (with S. Fujita), to appear in Graphs and Combinatorics.
  9. Hadwiger's conjecture is decidable (with B. Reed), to appear in the 41st ACM Symposium on Theory of Computing (STOC'09).
  10. Three-coloring triangle-free planar graphs in linear time (with Z. Dvorak and R. Thomas), to appear in ACM transaction on Algorithms.
  11. Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs, (with E. Demaine and M. Hajaghayi), to appear in ICALP'09.
  12. Minors in 5-connected non-planar large graphs (with J. Maharry), to appear in J. Graph Theory.
  13. Even disjoint cycles packing (with S. Chiba, S. Fujita and T. Sakuma), to appear in Eurocomb'09.
  14. Planarity allowing few errors in linear time, to appear in 50th Annual Symposium on Foundations of Computer Science (FOCS 2009)
  15. Non-separating even cycles in highly connected graphs (with S. Fujita), to appear in Combinatorica.
  16. Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs (with E. Demaine and M. Hajiaghayi), to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'10).
  17. The edge disjoint paths problem in Eulerian graphs and $4$-edge-connected graphs (with Y. Kobayashi), to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'10).
  18. An (almost) Linear Time Algorithm For Odd Cycles Transversal (with B. Reed), to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'10).
  19. Recognizing a totally odd $K_4$-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements (with Z. Li and B. Reed), to appear in ACM-SIAM Symposium on Discrete Algorithms, (SODA'10).
  20. Matching extension versus representativity in 5-connected embedded graphs (with S. Negami, M. Plummer and Y. Suzuki), to appear in J. Combin. Theory Ser. B.
  21. A simple algorithm for 4-coloring 3-colorable planar graphs (with K. Ozeki), to appear in Theoretical Computer Science.
  22. A note on traversing specified vertices in graphs embedded with large representativity (with M. Plummer), to appear in Discrete Math (Carsten Thomassen's 60).
  23. Odd cycle packing (with B. Reed), to appear in 42nd ACM Symposium on Theory of Computing (STOC'10).
  24. A shorter proof of the Graph Minor Algorithm - The Unique Linkage Theorem - (with P. Wollan), to appear in 42nd ACM Symposium on Theory of Computing (STOC'10).

 

News:

  1. SODA'12 will take place in Kyoto, Japan!
  2. As of Nov. 1, 2009, I am Professor of National Institute of Informatics.
  3. Inoue Research Award, 2009, February.
  4. Japan IBM Science Prize in Computer Science, November, 2008.
  5. I am on the Program Committee of SODA11, Annual ACM-SIAM Symposium on Discrete Algorithms, 2011.
  6. I am on the Program Committee of Siam Discrete Math Conference, 2010.
  7. 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.
  8. I am co-organizing a workshop "Bertinoro workshop on Graphs and Algorithm", Bertinoro, 2009, Dec.
  9. I am on the Program Committee of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010), August, 2010.
  10. Young Researchers Prize from Ministry of Education, Culture, Sports, and Science and Technology (Monka Syo) , 2006 April.
  11. Best Paper from The 17th International Symposium on Algorithms and Computation (ISAAC 2006).
  12. 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.