Ken-ichi Kawarabayashi

Profile Information

Affiliation: -
: The Graduate University for Advanced Studies
: Japan Science and Technology Agency

Degree: 理学

J-GLOBAL ID: 201101014264069073
researchmap Member ID: B000000202

External link: http://research.nii.ac.jp/~k_keniti/

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

Research Interests

Research Areas

Informatics / Information theory /

Research History

May, 2024 - Present

Program Officer, Broadening Opportunities for Outstanding young researchers and doctoral students in Strategic areas, JST BOOST
Sep, 2023 - Present

JST 創発的研究支援事業アドバイザー
Jul, 2023 - Present

文部科学省共同利用・共同研究システム形成事業「学際領域展開ハブ形成プログラム」推進委員会委員
May, 2023 - Present

独立行政法人大学改革支援・学位授与機構大学・高専機能強化支援事業選定委員会専門委員
Apr, 2023 - Present

JSPS デジタルと掛けるダブルメジャー大学院教育構築事業委員会委員
Sep, 2022 - Present

JST 研究開発戦略センター分野別委員会委員
Apr, 2022 - Present

Professor, The Graduate School of Information Science and Technology Department of Computer Science, The University of Tokyo
Apr, 2021 - Present

文部科学省科学技術・学術審議会臨時委員
Jun, 2020 - Present

Advisor, Industry-academia Collaborative R&D, JST A-STEP
Nov, 2019 - Present

Chief Implementation Officer/Cordinator, Experts of Information Science, JST GSC
Nov, 2009 - Present

Professor, Principle of Informatics Research Division, National Institute of Informatics
Apr, 2019 - Mar, 2025

Research Supervisor, JST ACT-X Frontier of mathematics and information science
Apr, 2018 - Mar, 2022

Program Officer, Research Center for Science Systems, Japan Soceity for the Promotion of Scinece
Apr, 2019 - Mar, 2021

Deputy Director General, National Institute of Informatics
Jul, 2017 - Mar, 2021

Research Area Advisor, Information and Future, JST-ACT-I
Oct, 2012 - Mar, 2019

Research Director, JST ERATO Kawarabayashi Large Graph Project
Apr, 2006 - Oct, 2009

Associate Professor, Principle of Informatics Research Division, National Institute of Informatics
Aug, 2003 - Mar, 2006

Assistant Professor, Graduate School of Information Sciences, Tohoku University

Awards

Oct, 2024

Humboldt Research Award, Alexander von Humboldt Foundation
Jul, 2021

The Fulkerson Prize for 2021, Deterministic Edge Connectivity in Near-Linear Time, Mathematical Optimization Society, American Mathematical Society

Ken-ichi Kawarabayashi, Mickkel Thorup
Mar, 2015

2015 MSJ Spring Prize, The Mathematical Society of Japan

Ken-ichi Kawarabayashi
Feb, 2013

9th (FY2012) JSPS Prize, Japan Society for the Promotion of Science

Ken-ichi Kawarabayashi
Jan, 2013

Best Paper Awards, ACM-SIAM Symposium on Discrete Algorithms（SODA）

Ken-ichi Kawarabayashi
Apr, 2011

10th Funai Science Prize Tetsuyoshi Funai Special Award, the Funai Foundation for Information Science

Ken-ichi Kawarabayashi
Feb, 2009

2009 Inoue Prize for Science, Inoue Foundation for Science

Ken-ichi Kawarabayashi
Nov, 2008

Japan IBM Science Prize, Japan IBM

Ken-ichi Kawarabayashi
Jan, 2007

The Organizing Committee of ISAAC 2006 presents the Best Paper Award, 17th International Symposium on Algorithms and Computation

Ken-ichi Kawarabayashi
Apr, 2006

Young Scientists’ Prize, Commendation for Science and Technology, Ministry of Education, Culture, Sport, Science and Technology
Dec, 2003

Inoue Research Award for Young Scientists, Inoue Foundation for Science

Ken-ichi Kawarabayashi
Sep, 2001

2001 MSJ Takebe Katahiro Prize, The Mathematial Society of Japan

Misc.

Coherent Ising machines-optical neural networks operating at the quantum limit

Yoshihisa Yamamoto, Kazuyuki Aihara, Timothee Leleu, Ken-ichi Kawarabayashi, Satoshi Kako, Martin Fejer, Kyo Inoue, Hiroki Takesue

NPJ QUANTUM INFORMATION, 3, Dec, 2017 Peer-reviewed
Combinatorial optimization and graph algorithms: Communications of NII Shonan meetings

Takuro Fukunaga, Ken-Ichi Kawarabayashi

Combinatorial Optimization and Graph Algorithms: Communications of NII Shonan Meetings, 1-120, Oct 2, 2017
Preface

Takuro Fukunaga, Ken-Ichi Kawarabayashi

Combinatorial Optimization and Graph Algorithms: Communications of NII Shonan Meetings, v-vii, Oct 2, 2017
劣モジュラ評価関数をもつ最適価格付け問題

前原貴憲, 前原貴憲, 河瀬康志, 澄田範奈, 東野克哉, 河原林健一

日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2017, 2017
Optimal Pricing for Submodular Valuations with Bounded Curvature.

Takanori Maehara, Yasushi Kawase, Hanna Sumita, Katsuya Tono, Ken-ichi Kawarabayashi

CoRR, abs/1611.07605, 2016
イマージョンを含まないグラフに対する彩色アルゴリズム

垣村尚徳, 河原林健一, 河原林健一

日本応用数理学会年会講演予稿集(CD-ROM), 2016 ROMBUNNO.9GATSU13NICHI,11:00,3E,3, 2016
学術情報ネットワークにおける最適キャッシュ配置

横井優, NGUYEN Hau Than, 松岡達也, 小林佑輔, 垣村尚徳, 河原林健一

日本応用数理学会年会講演予稿集(CD-ROM), 2015 ROMBUNNO.9GATSU9NICHI,09:30,A,2, Sep 2, 2015
整数格子劣モジュラ関数の適応的最大化 (コンピュテーション)

波多野大督, 福永拓郎, 河原林健一

電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 115(84) 1-8, Jun 12, 2015
完全動的索引によるグラフ上の影響力推定・影響最大化クエリ

大坂直人, 秋葉拓哉, 吉田悠一, 河原林健一

人工知能学会全国大会, May, 2015
23pAK-8 A distinctive class of users as a characteristic of online communication networks

Takaguchi T., Maehara T., Toyoda M., Kawarabayashi K.

Meeting Abstracts of the Physical Society of Japan, 70(1) ROMBUNNO.23PAK-8-3127, Mar 24, 2015
枝刈り探索によるソーシャルネットワークでの影響最大化アルゴリズム

大坂直人, 秋葉拓哉, 吉田悠一, 河原林健一

第6回データ工学と情報マネジメントに関するフォーラム(DEIM), Mar, 2014
2-F-2 二部グラフ上の最適予算配分問題に対する高速アルゴリズム(離散最適化(4))

相馬輔, 垣村尚徳, 河原林健一

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2013 246-247, Sep 11, 2013
Testing Subdivision-Freeness: - Property Testing Meets Structural Graph Theory -

Ken-ichi Kawarabayashi, Yuichi Yoshida

IPSJ SIG Notes, 2013(18) 1-5, May 10, 2013
Introduction on JST ERATO Kawarabayashi Large Graph Project

KAWARABAYASHI Ken-ichi

IEICE technical report. Theoretical foundations of Computing, 113(14) 25-25, Apr 17, 2013
Hamiltonicity of 4-connected projective-planar graphs

Kawarabayashi Ken-ichi, Ozeki Kenta

IEICE technical report. Theoretical foundations of Computing, 112(340) 23-23, Dec 3, 2012
DS-1-8 A spanning closed walk of 3-connected plane graphs

Kawarabayashi Ken-ichi, Ozeki Kenta

Proceedings of the IEICE General Conference, 2012(1) "S-15"-"S-16", Mar 6, 2012
指定された頂点を通るパリティ制約付サイクルのパッキング

垣村尚徳, 河原林健一

日本応用数理学会年会講演予稿集, 2011 125-126, 2011
2-F-10 平面グラフ上の誘導サイクル問題に対する解法(グラフ(1))

河原林健一, 小林佑輔

日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2008 306-307, Sep 10, 2008

Presentations

離散数学、グラフアルゴリズムの国際研究

河原林健一

情報処理学会第87回全国大会, Mar 13, 2025 Invited
Three-edge coloring cubic graphs on surface of ow genus

Ken-ichi Kawarabayashi

WALCOM 2025,, Mar 2, 2025 Invited
Three-edge-coloring (Tait coloring) projective planar cubic graphs: A generalization of the Four Color Theorem

Ken-ichi Kawarbayashi

BARC double talk by Mohar and Kawarabayashi, Sep 16, 2024 Invited
Three-edge-coloring projective planar cubic graphs: A generalization of the Four Color Theorem

Ken-ichi Kawarabayashi

COCOON 2024, Aug 23, 2024 Invited
Three-edge-coloring projective planar cubic graphs: A generalization of the Four Color Theorem

Ken-ichi Kawarabayashi

Fulkerson 100, The Dept. of Combinatorics & Optimization (C&O) at the University of Waterloo, Jul 19, 2024 Invited
three-edge-coloring and the four color theorem

河原林健一

離散数学とその応用１日研究集会－加納幹雄先生応用数学賞受賞記念集会－, Jun 29, 2024 Invited
古典アルゴリズムとの比較：数理的な正当性と近似アルゴリズム

河原林健一

2024年電気情報通信学会総合大会, Mar 7, 2024 Invited
Toward the directed graph minor theory

Ken-ichi Kawarabayashi

TGT35, Nov 9, 2023 Invited
Computing Canonical Graph Decompositions

Ken-ichi Kawarabayashi

10TH SLOVENIAN CONFERENCE ON GRAPH THEORY, Jun, 2023 Invited
Recent progress on Directed Graph Minor

Ken-ichi Kawarabayashi

8th Czech-Slovak International Symposium on Graph Theory, Combinatorics, Algorithms and Applications, Jul, 2022 Invited
「情報科学の達人」の取り組み

河原林健一

第28回画像センシングシンポジウム(SSII2022), Jun, 2022 Invited
「情報科学の達人」プログラムの初年度と今後の展望

河原林健一

情報処理学会第84回全国大会, Mar, 2022 Invited
Toward Directed Graph Minor Theory

Ken-ichi Kawarabayashi

Virtual Discrete Math Colloquium@IBS Discrete Mathematics Group, Jan 20, 2022 Invited
Low diameter decomposition, polylogarithmic approximation for directed sparsest-cut, and embedding into directed ℓ1 for directed planar graph ↑

Ken-ichi Kawarabayashi

Oct 18, 2021 Invited
Directed Graph Minor

Ken-ichi Kawarabayashi

ICNTDM 2020, Dec, 2020 Invited
Graph and Network structure: Theory, Algorithm and implementation

Ken-ichi Kawarabayashi

@Nanjing University academic week, Jun, 2020 Invited
The Directed Flat Wall Theorem

河原林健一

電子情報通信学会 COMP研究会, May, 2020 Invited
Algorithmic Topological Graph Theory

Ken-ichi Kawarabayashi

42th ACCMCC, Dec, 2019 Invited
Some algorithmic aspect using the Four Color Theorem

Ken-ichi Kawarabayashi

Waterloo Coloring Conference 2019, Sep, 2019 Invited
Directed Graph Minors

Ken-ichi Kawarabayashi

30th Workshop on Topological Graph Theory, Oct, 2018 Invited

Papers

347

A Metric Differential Privacy Mechanism for Sentence Embeddings

Danushka Bollegala, Shuichi Otake, Tomoya Machide, Ken-ichi Kawarabayashi

ACM Transactions on Privacy and Security, 28(2) 1-34, Feb 22, 2025 Peer-reviewed
An analogue of Reed's conjecture for digraphs.

Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta

SODA, 3310-3324, 2025 Peer-reviewed
Automorphisms and Isomorphisms of Maps in Linear Time.

Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela, Peter Zeman 0001

ACM Trans. Algorithms, 21(1) 6-32, Jan, 2025
A half-integral Erdős-Pósa theorem for directed odd cycles.

Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon, Qiqin Xie

J. Comb. Theory B, 172 115-145, 2025 Peer-reviewed
Three-Edge-Coloring Projective Planar Cubic Graphs: A Generalization of the Four Color Theorem.

Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Tomohiro Sonobe

FOCS, 86-105, 2024 Peer-reviewed
Edge-Disjoint Paths in Eulerian Digraphs.

Dario Giuliano Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer

STOC, 704-715, 2024 Peer-reviewed
Packing Even Directed Circuits Quarter-Integrally.

Maximilian Gorsky, Ken-ichi Kawarabayashi, Stephan Kreutzer, Sebastian Wiederrecht

STOC, 692-703, 2024 Peer-reviewed
Better Coloring of 3-Colorable Graphs.

Ken-ichi Kawarabayashi, Mikkel Thorup, Hirotaka Yoneda

STOC, 331-339, 2024 Peer-reviewed
New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem.

Koji Ichikawa, Shinji Ito, Daisuke Hatano, Hanna Sumita, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi

AAAI, 12708-12716, 2024 Peer-reviewed
Optimal distributed covering algorithms.

Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, Gregory Schwartzman

Distributed Comput., 36(1) 45-55, Mar, 2023 Peer-reviewed
Bandit Task Assignment with Unknown Processing Time.

Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi

NeurIPS, 2023 Peer-reviewed
A half-integral Erdős-Pósa theorem for directed odd cycles.

Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon, Qiqin Xie

SODA, 3043-3062, 2023 Peer-reviewed
Rooted topological minors on four vertices.

Koyo Hayashi, Ken-ichi Kawarabayashi

J. Comb. Theory, Ser. B, 158(Part) 146-185, 2023 Peer-reviewed
Additive non-approximability of chromatic number in proper minor-closed classes.

Zdenek Dvorák, Ken-ichi Kawarabayashi

J. Comb. Theory, Ser. B, 158(Part) 74-92, 2023 Peer-reviewed
Directed Tangle Tree-Decompositions and Applications.

Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, O-joung Kwon

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms(SODA), 377-405, 2022 Peer-reviewed
Query Obfuscation by Semantic Decomposition.

Danushka Bollegala, Tomoya Machide, Ken-ichi Kawarabayashi

LREC, 6200-6211, 2022 Peer-reviewed
Online Task Assignment Problems with Reusable Resources.

Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi

AAAI, 5199-5207, 2022 Peer-reviewed
The Effect of Random Projection on Local Intrinsic Dimensionality.

Michael E. Houle, Ken-ichi Kawarabayashi

Similarity Search and Applications - 14th International Conference(SISAP), 201-214, 2021 Peer-reviewed
How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks.

Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-ichi Kawarabayashi, Stefanie Jegelka

9th International Conference on Learning Representations(ICLR), 2021 Peer-reviewed
Automorphisms and Isomorphisms of Maps in Linear Time.

Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela, Peter Zeman 0001

48th International Colloquium on Automata, Languages, and Programming(ICALP), 86-15, 2021 Peer-reviewed

Research Projects

離散数学、グラフアルゴリズム、グラフ理論の横断的研究

ASPIRE 先端国際共同研究推進事業, AI・情報, 国立研究開発法人科学技術振興機構, Feb, 2024 - Mar, 2029
Graph Algorithms and Optimization: Theory and Scalable Algorithms

Grants-in-Aid for Scientific Research, Grant-in-Aid for Scientific Research (S), Japan Society for the Promotion of Science, Apr, 2022 - Mar, 2027
New computational models for algorithms and discrete optimization

Grants-in-Aid for Scientific Research, Grant-in-Aid for Transformative Research Areas (A), Japan Society for the Promotion of Science, Nov, 2020 - Mar, 2025
Research Initiatives on Algorithmic Foundations for Social Advancement

Grants-in-Aid for Scientific Research, Grant-in-Aid for Transformative Research Areas (A), Japan Society for the Promotion of Science, Nov, 2020 - Mar, 2025
Large Graphs: Theory and Algorithms

Grants-in-Aid for Scientific Research, Grant-in-Aid for Scientific Research (S), Japan Society for the Promotion of Science, Jun, 2018 - Mar, 2023
TSP in Combinatorial Optimization and CSP in Theoretical Computer Science

Grants-in-Aid for Scientific Research, Grant-in-Aid for JSPS Fellows, Japan Society for the Promotion of Science, Nov, 2018 - Mar, 2021
Interconnection networks approaching the theoretical limit

Grants-in-Aid for Scientific Research, Grant-in-Aid for Scientific Research (C), Japan Society for the Promotion of Science, Apr, 2015 - Mar, 2018

Fujiwara Ikki, Koibuchi Michihiro, Kawarabayashi Ken-ichi, Fujita Satoshi, Nakano Koji, Takafuji Daisuke, Matsutani Hiroki, Yasudo Ryota
Studies on Limits of Computation via Information and Coding Theory

Grants-in-Aid for Scientific Research, Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), Japan Society for the Promotion of Science, Jun, 2012 - Mar, 2017

Kawarabayashi Kenichi
A Multifaced Approach Toward Understanding the Limitations of Compuation

Grants-in-Aid for Scientific Research, Grant-in-Aid for Scientific Research on Innovative Areas (Research in a proposed research area), Japan Society for the Promotion of Science, Jun, 2012 - Mar, 2017

Watanabe Osamu, ASANO Takao, IBARAKI Toshihide, IMAI Hiroshi, TODA Seinosuke, MARUOKA Akira, MINATO Shinichi, MAKINO Kazuhisa, KAWARABAYASHI Kazuhisa, ASANO Tetsuo, KATOH Naoki, AVIS David, TOKUYAMA Takeshi, YAMASHITA Shigeru, TAKIMOTO Eiji, HORIYAMA Takashi, MORI Ryuhei
structural graph theory and eifficient algorithm for graph coloring problems

Grants-in-Aid for Scientific Research, Grant-in-Aid for Young Scientists (A), Japan Society for the Promotion of Science, Apr, 2009 - Mar, 2013

KAWARABAYASHI Ken-ichi
グラフ理論、離散数学のスケジューリング問題への応用

科学研究費助成事業, 特別研究員奨励費, 日本学術振興会, 2011 - 2012

河原林健一, HOSHINO Richard
A study on the distance structure and the connectivity structure of graphs

Grants-in-Aid for Scientific Research, Grant-in-Aid for Scientific Research (B), Japan Society for the Promotion of Science, 2008 - 2011

ANDO Kiyoshi, EGAWA Yoshimi, KAWARABAYASHI Ken-ichi
アルゴリズム的グラフマイナー理論

科学研究費助成事業, 挑戦的萌芽研究, 日本学術振興会, 2009 - 2010

河原林健一
計算理論的設計による知識抽出モデルに関する研究

科学研究費助成事業, 特定領域研究, 日本学術振興会, 2004 - 2007

徳山豪, 塩浦昭義, 河原林健一, 全眞嬉
グラフ彩色問題における4色定理の応用、拡張に関する研究

科学研究費助成事業, 若手研究(B), 日本学術振興会, 2004 - 2006

河原林健一
Research on data rounding based on discrete systems.

Grants-in-Aid for Scientific Research, Grant-in-Aid for Scientific Research (C), Japan Society for the Promotion of Science, 2004 - 2005

TOKUYAMA Takeshi, KAWARABAYASHI Kenichi
Fundamental and application oriented studies of discrete structures

Grants-in-Aid for Scientific Research, Grant-in-Aid for Scientific Research (C), Japan Society for the Promotion of Science, 2002 - 2004

ANDO Kiyoshi, ISHIGAMI Yoshiyasu, KAWARABAYASHI Ken-ichi
グラフ理論における道と閉路と連結度に関する研究

科学研究費助成事業, 特別研究員奨励費, 日本学術振興会, 2000 - 2002

河原林健一

Profile Information

Research Interests

Research Areas

Research History

Awards

Misc.

Presentations

Papers

Research Projects

Menu

Coauthors

Following