2024/07/28 更新

お知らせ

 

写真a

キムラ　ケイ
木村 慧
KIMURA KEI
所属
システム情報科学研究院 情報学部門 准教授
工学部 電気情報工学科（併任）
システム情報科学府 情報理工学専攻（併任）
マス・フォア・イノベーション連係学府 （併任）
職名
准教授
プロフィール
広くは計算機科学，数理工学，応用数学，より詳細には組合せ最適化，離散アルゴリズムの研究に従事
ホームページ
外部リンク

学位

  • 博士（情報理工学）

研究テーマ・研究キーワード

  • 研究テーマ：数理最適化，アルゴリズム，メカニズムデザイン，理論計算機科学

    研究キーワード：整数線形最適化，離散構造，マッチング，計算複雑さ

    研究期間： 2022年6月

受賞

  • 準優秀賞

    2022年3月   SMASH22 WINTER SYMPOSIUM 実行委員会   マルチエージェント経路探索アルゴリズムの 改良のための一検討

  • 令和3年度ベストレクチャー賞

    2021年11月   埼玉大学 工学部  

  • 令和2年度ベストレクチャー賞

    2020年12月   埼玉大学 工学部  

  • 系長賞

    2018年11月   豊橋技術科学大学 情報・知能工学系  

  • 最優秀論文賞

    2013年3月   電子情報通信学会   整数線形不等式系の実行可能性問題に対する符号情報に基づく計算複雑さの指標

  • 最優秀発表賞受賞

    2011年6月   日本オペレーションズ・リサーチ学会「計算と最適化の新展開」研究部会   整数線形システムの実行可能性問題に対する計算複雑さの指標

▼全件表示

論文

  • Fairness and efficiency trade-off in two-sided matching.

    Sung-Ho Cho, Kei Kimura, Kiki Liu, Kwei-guu Liu, Zhengjie Liu, Zhaohong Sun 0001, Kentaro Yahiro, Makoto Yokoo

    CoRR   abs/2402.01084   2024年2月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.48550/arXiv.2402.01084

  • Characterizing the integer points in 2-decomposable polyhedra by closedness under operations.

    Kei Kimura, Kazuhisa Makino, Shota Yamada, Ryo Yoshizumi

    CoRR   abs/2401.06405   2024年1月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.48550/arXiv.2401.06405

  • A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems.

    Kei Kimura, Kazuhisa Makino

    ISAAC   47 - 17   2023年12月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（その他学術会議資料等）  

    DOI： 10.4230/LIPIcs.ISAAC.2023.47

  • Multi-Stage Generalized Deferred Acceptance Mechanism: Strategyproof Mechanism for Handling General Hereditary Constraints.

    Kei Kimura, Kwei-guu Liu, Zhaohong Sun 0001, Kentaro Yahiro, Makoto Yokoo

    CoRR   abs/2309.10968   2023年9月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.48550/arXiv.2309.10968

  • A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems.

    Kei Kimura, Kazuhisa Makino

    CoRR   abs/2306.03368   2023年6月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.48550/arXiv.2306.03368

  • Algorithms for coloring reconfiguration under recolorability digraphs 査読

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura, Akira Suzuki

    Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022)   4:1 - 4:19   2022年12月

    　詳細を見る

    記述言語：その他  

    Algorithms for coloring reconfiguration under recolorability digraphs

    DOI： 10.4230/LIPIcs.ISAAC.2022.4

  • Neighborhood Persistency of the Linear Optimization Relaxation of Integer Linear Optimization 査読

    312 - 323   2022年11月

    　詳細を見る

    記述言語：その他  

    DOI： 10.1007/978-3-031-18530-4_23

  • Quantaloidal approach to constraint satisfaction 査読

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura

    Proceedings of the 4th International Conference on Applied Category Theory (ACT 2021)   EPTCS 372   289 - 305   2022年10月

    　詳細を見る

    記述言語：その他  

    Quantaloidal approach to constraint satisfaction

  • Neighborhood persistency of the linear optimization relaxation of integer linear optimization

    Kei Kimura, Kotaro Nakayama

    CoRR   arXiv:2203.04557   312 - 323   2022年3月

    　詳細を見る

    記述言語：その他  

    DOI： 10.1007/978-3-031-18530-4_23

  • Computational complexity of three-dimensional discrete tomography with missing data 査読

    Kei Kimura, Takuya Kamehashi

    Japan Journal of Industrial and Applied Mathematics   38 ( 3 )   823 - 858   2021年9月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1007/s13160-021-00464-0

  • Quantaloidal approach to constraint satisfaction.

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura

    CoRR   abs/2107.01778   2021年7月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

  • Optimal Matroid Partitioning Problems 査読

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita

    Algorithmica   83 ( 6 )   1653 - 1676   2021年6月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1007/s00453-021-00797-9

  • Trichotomy for the reconfiguration problem of integer linear systems. 査読

    Kei Kimura, Akira Suzuki

    Theor. Comput. Sci.   856   88 - 109   2021年2月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1016/j.tcs.2020.12.025

  • Stronger Hardness Results on the Computational Complexity of Picross 3D 査読

    Kei KIMURA

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences   E103.A ( 4 )   668 - 676   2020年4月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1587/transfun.2019eap1101

  • Trichotomy for the Reconfiguration Problem of Integer Linear Systems. 査読

    Kei Kimura, Akira Suzuki

    Proceedings of the 14th International Conference and Workshops on Algorithms and Computation, LNCS 12049   336 - 341   2020年3月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（その他学術会議資料等）  

    Trichotomy for the Reconfiguration Problem of Integer Linear Systems.
    In this paper, we consider the reconfiguration problem of integer linear<br />
    systems. In this problem, we are given an integer linear system &#36;I&#36; and two<br />
    feasible solutions &#36;oldsymbol{s}&#36; and &#36;oldsymbol{t}&#36; of &#36;I&#36;, and then asked<br />
    to transform &#36;oldsymbol{s}&#36; to &#36;oldsymbol{t}&#36; by changing a value of only<br />
    one variable at a time, while maintaining a feasible solution of &#36;I&#36;<br />
    throughout. &#36;Z(I)&#36; for &#36;I&#36; is the complexity index introduced by Kimura and<br />
    Makino (Discrete Applied Mathematics 200:67--78, 2016), which is defined by the<br />
    sign pattern of the input matrix. We analyze the complexity of the<br />
    reconfiguration problem of integer linear systems based on the complexity index<br />
    &#36;Z(I)&#36; of given &#36;I&#36;. We then show that the problem is (i) solvable in constant<br />
    time if &#36;Z(I)&#36; is less than one, (ii) weakly coNP-complete and<br />
    pseudo-polynomially solvable if &#36;Z(I)&#36; is exactly one, and (iii)<br />
    PSPACE-complete if &#36;Z(I)&#36; is greater than one. Since the complexity indices of<br />
    Horn and two-variable-par-inequality integer linear systems are at most one,<br />
    our results imply that the reconfiguration of these systems are in coNP and<br />
    pseudo-polynomially solvable. Moreover, this is the first result that reveals<br />
    coNP-completeness for a reconfiguration problem, to the best of our knowledge.

    DOI： 10.1007/978-3-030-39881-1_29

  • NP-Completeness of Fill-a-Pix and Sigma(P)(2)-Completeness of Its Fewest Clues Problem 査読

    Higuchi Yuta, Kimura Kei

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E102A ( 11 )   1490 - 1496   2019年11月

    　詳細を見る

    記述言語：その他  

    NP-Completeness of Fill-a-Pix and Sigma(P)(2)-Completeness of Its Fewest Clues Problem

    DOI： 10.1587/transfun.E102.A.1490

  • Trichotomy for the reconfiguration problem of integer linear systems.

    Kei Kimura, Akira Suzuki

    CoRR   abs/1911.02786   2019年11月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

  • Approximating Partially Bounded Degree Deletion on Directed Graphs 査読

    Toshihiro Fujito, Kei Kimura, Yuki Mizuno

    Journal of Graph Algorithms and Applications   23 ( 5 )   759 - 780   2019年10月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.7155/jgaa.00511

  • A Fast Algorithm for Unbounded Monotone Integer Linear Systems with Two Variables per Inequality via Graph Decomposition. 査読

    Takuya Tamori, Kei Kimura

    WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Guwahati, India, February 27 - March 2, 2019, Proceedings   209 - 218   2019年2月

    　詳細を見る

    記述言語：その他  

    A Fast Algorithm for Unbounded Monotone Integer Linear Systems with Two Variables per Inequality via Graph Decomposition.

    DOI： 10.1007/978-3-030-10564-8_17

  • Linear Satisfiability Preserving Assignments (Extended Abstract).

    Kei Kimura, Kazuhisa Makino

    Proceedings of the 27th International Joint Conference on Artificial Intelligence   5622 - 5626   2018年7月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（その他学術会議資料等）  

    Linear Satisfiability Preserving Assignments (Extended Abstract).

    DOI： 10.24963/ijcai.2018/797

  • Maximum lifetime coverage problem with battery recovery effect 査読

    Norie Fu, Naonori Kakimura, Kei Kimura, Vorapong Suppakitpaisarn

    Sustainable Computing: Informatics and Systems   18   1 - 13   2018年6月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1016/j.suscom.2018.02.007

  • The Fewest Clues Problem of Picross 3D. 査読

    Kei Kimura, Takuya Kamehashi, Toshihiro Fujito

    9th International Conference on Fun with Algorithms, FUN 2018, June 13-15, 2018, La Maddalena, Italy   25:1-25:13   2018年6月

    　詳細を見る

    記述言語：その他  

    The Fewest Clues Problem of Picross 3D.

  • Approximating Partially Bounded Degree Deletion on Directed Graphs 査読

    Toshihiro Fujito, Kei Kimura, Yuki Mizuno

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10755   32 - 43   2018年3月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

    DOI： 10.1007/978-3-319-75172-6_4

  • Autark assignments of Horn CNFs 査読

    Kei Kimura, Kazuhisa Makino

    Japan Journal of Industrial and Applied Mathematics   35 ( 1 )   297 - 309   2018年3月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1007/s13160-017-0284-6

  • Linear Satisfiability Preserving Assignments 査読

    Kei Kimura, Kazuhisa Makino

    Journal of Artificial Intelligence Research   61   291 - 321   2018年2月

    　詳細を見る

    記述言語：その他   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1613/jair.5658

    リポジトリ公開URL： https://hdl.handle.net/2324/7172672

  • Optimal matroid partitioning problems 査読

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita

    Leibniz International Proceedings in Informatics, LIPIcs   92   51:1-51:13   2017年12月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

    DOI： 10.4230/LIPIcs.ISAAC.2017.51

  • Optimal Matroid Partitioning Problems 査読

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita

    CoRR   abs/1710.00950   2017年10月

    　詳細を見る

    記述言語：その他  

    Optimal Matroid Partitioning Problems

  • Trichotomy for integer linear systems based on their sign patterns 査読

    Kei Kimura, Kazuhisa Makino

    DISCRETE APPLIED MATHEMATICS   200   67 - 78   2016年2月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1016/j.dam.2015.07.004

  • Maximum Lifetime Coverage Problems with Battery Recovery Effects 査読

    Norie Fu, Vorapong Suppakitpaisarn, Kei Kimura, Naonori Kakimura

    2014 IEEE GLOBAL COMMUNICATIONS CONFERENCE (GLOBECOM 2014)   118 - 124   2014年12月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

    DOI： 10.1109/GLOCOM.2014.7036794

  • Satisfiability Preserving Assignments and Their Local and Linear Forms

    Kei Kimura, Kazuhisa Makino

    MATHEMATICAL ENGINEERING TECHNICAL REPORTS   2014-34, University of Tokyo   2014年11月

    　詳細を見る

    記述言語：その他  

    Satisfiability Preserving Assignments and Their Local and Linear Forms

  • Trichotomy for Integer Linear Systems Based on Their Sign Patterns 査読

    Kei Kimura, Kazuhisa Makino

    29TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, (STACS 2012)   14   613 - 623   2012年3月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

    DOI： 10.4230/LIPIcs.STACS.2012.613

  • Trichotomy for Integer Linear Systems Based on Their Sign Patterns

    Kei Kimura, Kazuhisa Makino

    MATHEMATICAL ENGINEERING TECHNICAL REPORTS   METR 2012-2, University of Tokyo   2012年1月

    　詳細を見る

    記述言語：その他  

    Trichotomy for Integer Linear Systems Based on Their Sign Patterns

▼全件表示

講演・口頭発表等

  • 時間相関イメージセンサと多重極変調リング照明を用いた表面検査 (第25回センシングフォーラム資料--センシング技術の新たな展開と融合) -- (センサ(2))

    栗原 徹, 持田 康弘, 木村 慧

    センシングフォ-ラム資料  2008年9月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • 整数線形システムの実行可能性問題に対する計算複雑さの指標

    木村慧

    木村慧, 牧野和久, 日本オペレーションズ・リサーチ学会「計算と最適化の新展開」研究部会（SCOPE@つくば）, 筑波大学  2011年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 整数線形システムの実行可能性問題に対する計算複雑さの指標

    木村慧

    木村慧, 牧野和久, 日本オペレーションズ・リサーチ学会, 甲南大学  2011年9月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 整数線形システムの実行可能性問題に対する計算複雑さの指標

    木村慧, 牧野和久

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集  2011年9月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • 2-I-4 整数線形システムの実行可能性問題に対する計算複雑さの指標(離散最適化(3))

    木村 慧, 牧野 和久

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集  2011年9月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • Trichotomy for Integer Linear Systems Based on Their Sign Patterns

    Kei Kimura

    Kei Kimura and Kazuhisa Makino, The 29th Symposium on Theoretical Aspects of Computer Science (STACS 2012), Paris, France  2012年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Trichotomy for Integer Linear Systems Based on Their Sign Patterns

  • 整数線形不等式系の実行可能性問題に対する符号情報に基づく計算複雑さの指標

    木村慧

    木村慧, 牧野和久, 電子情報通信学会, 岐阜大学  2013年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 整数線形不等式系の実行可能性問題に対する符号情報に基づく計算複雑さの指標

    木村慧, 牧野和久

    電子情報通信学会大会講演論文集  2013年3月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • DS-1-6 整数線形不等式系の実行可能性問題に対する符号情報に基づく計算複雑さの指標(DS-1.COMP学生シンポジウム,シンポジウムセッション)

    木村 慧, 牧野 和久

    電子情報通信学会総合大会講演論文集  2013年3月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • A Complexity Index for Integer Linear Systems Based on Their Sign Patterns

    Kei Kimura

    Kei Kimura and Kazuhisa Makino, The 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2013), Veszprem, Hungary  2013年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    A Complexity Index for Integer Linear Systems Based on Their Sign Patterns

  • Maximum Lifetime Coverage Problems with Battery Recovery Effects

    V. Suppakitpaisarn

    F. Norie, V. Suppakitpaisarn, K. Kimura, N. Kakimura, Forum on Information Technology: Special Section on Advanced Topics on Basic Research, Tottori University (Poster Presentation)  2013年9月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 制約充足問題に対する線形固定可能割当ての解析

    木村慧

    木村慧, 牧野和久, 日本オペレーションズ・リサーチ学会, 大阪大学  2014年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 制約充足問題に対する線形固定可能割当ての解析

    木村慧

    木村慧, 牧野和久, 電子情報通信学会, 新潟大学  2014年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • A Complexity Index of Integer Linear Systems Based on Their Sign Patterns 招待 国際会議

    the 63th KPPY Combinatorics Workshop, Daegu, Korea  2014年3月 

    　詳細を見る

    記述言語：英語  

    国名：その他  

    A Complexity Index of Integer Linear Systems Based on Their Sign Patterns

  • 制約充足問題に対する線形固定可能割当ての解析

    木村慧, 牧野和久

    電子情報通信学会大会講演論文集(CD-ROM)  2014年3月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • 制約充足問題に対する線形固定可能割当ての解析

    木村慧, 牧野和久

    日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集  2014年3月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • DS-1-3 制約充足問題に対する線形固定可能割当ての解析(DS-1.COMP-ELC学生シンポジウム,シンポジウムセッション)

    木村 慧, 牧野 和久

    電子情報通信学会総合大会講演論文集  2014年3月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • 1-G-6 制約充足問題に対する線形固定可能割当ての解析(離散最適化(1))

    木村 慧, 牧野 和久

    日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集  2014年3月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • 制約充足問題に対する線形固定可能割当ての解析

    木村慧

    木村慧, 牧野和久, 日本オペレーションズ・リサーチ学会「最適化の理論と応用」研究部会SOTA, 筑波大学  2014年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • Maximum Lifetime Coverage Problems with Battery Recovery Effects

    Vorapong Suppakitpaisarn

    Norie Fu, Vorapong Suppakitpaisarn, Kei Kimura, and Naonori Kakimura, IEEE Global Communications Conference (GLOBECOM 2014), Austin, TX, USA  2014年12月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Maximum Lifetime Coverage Problems with Battery Recovery Effects

  • A Complexity Index for Integer Linear Systems Based on Their Sign Patterns

    Kei Kimura

    Kei Kimura and Kazuhisa Makino, ISAAC2015 preworkshop: ELC Workshop on Algorithms and Computation, Kyoto, Japan  2015年12月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    A Complexity Index for Integer Linear Systems Based on Their Sign Patterns

  • 整数線形不等式系の実行可能性問題における多項式時間可解部分クラス 招待

    木村慧

    2017年電子情報通信学会総合大会 COMP-ELC学生シンポジウム, 名城大学  2017年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 整数線形不等式系の実行可能性問題における多項式時間可解部分クラス

    木村慧

    電子情報通信学会大会講演論文集(CD-ROM)  2017年3月 

    　詳細を見る

    記述言語：日本語  

    国名：日本国  

  • Min-sum-max matroid partitioning problem

    Hanna Sumita

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, and Hanna Sumita, The 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2017), Budapest, Hungary  2017年5月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Min-sum-max matroid partitioning problem

  • Optimal Matroid Partitioning Problems

    Kei Kimura

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, and Hanna Sumita, The 28th International Symposium on Algorithms and Computation (ISAAC 2017), Phuket, Thailand  2017年12月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Optimal Matroid Partitioning Problems

  • ペンシルパズル「Fill-a-Pix」のNP完全性

    樋口雄太

    樋口雄太, 木村慧, 組合せゲーム・パズル(CGP)プロジェクト 第13回研究集会, 大阪府立大学  2018年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • ぷよを自由に配置できる場合のぷよぷよの連鎖数判定問題

    澁谷諒祐

    澁谷諒祐, 木村慧, 組合せゲーム・パズル(CGP)プロジェクト 第13回研究集会, 大阪府立大学  2018年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • Approximating Partially Bounded Degree Deletion on Directed Graphs

    Kei Kimura

    Toshihiro Fujito, Kei Kimura, and Yuki Mizuno, The 12th International Conference and Workshops on Algorithms and Computation (WALCOM 2018), Dhaka, Bangladesh  2018年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Approximating Partially Bounded Degree Deletion on Directed Graphs

  • ペンシルパズル「Fill-a-Pix」のNP完全性

    樋口雄太, 木村慧

    組合せゲーム・パズル(CGP)プロジェクト 第13回研究集会  2018年3月 

    　詳細を見る

    記述言語：その他  

    国名：日本国  

  • ぷよを自由に配置できる場合のぷよぷよの連鎖数判定問題

    澁谷諒祐, 木村慧

    組合せゲーム・パズル(CGP)プロジェクト 第13回研究集会  2018年3月 

    　詳細を見る

    記述言語：その他  

    国名：日本国  

  • The Fewest Clues Problem of Picross 3D

    Kei Kimura

    Kei Kimura, Takuya Kamehashi, and Toshihiro Fujito, The 9th International Conference on Fun with Algorithms (FUN 2018), La Maddalena, Italy  2018年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    The Fewest Clues Problem of Picross 3D

  • Linear Satisfiability Preserving Assignments (Extended Abstract)

    Kei Kimura

    Kei Kimura and Kazuhisa Makino, The 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), Stockholm, Seweden  2018年7月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Linear Satisfiability Preserving Assignments (Extended Abstract)

  • A Fast Algorithm for Unbounded Monotone Integer Linear Systems with Two Variables per Inequality via Graph Decomposition

    Takuya Tamori

    Takuya Tamori and Kei Kimura, The 13th International Conference and Workshops on Algorithms and Computation (WALCOM 2019), Guwahati, India  2019年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    A Fast Algorithm for Unbounded Monotone Integer Linear Systems with Two Variables per Inequality via Graph Decomposition

  • Three-dimensional discrete tomography with restriction on height and constraint numbers

    Kei Kimura

    Takuya Kamehashi and Kei Kimura, The 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (HJ 2019), Tokyo, Japan  2019年5月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Three-dimensional discrete tomography with restriction on height and constraint numbers

  • Computational complexity of the reconfiguration problem of integer linear systems

    2020年2月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Computational complexity of the reconfiguration problem of integer linear systems

  • 整数計画における遷移問題の計算量

    木村慧

    木村慧, 鈴木顕, 日本応用数理学会 第16回研究部会連合発表会, 中央大学  2020年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 制約充足問題に対する充足可能性保存割当ての解析 招待

    木村慧

    人工知能学会 第112回人工知能基本問題研究会(SIG-FPAI), 柳川市藤吉コミュニティセンター  2020年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • Trichotomy for the reconfiguration problem of integer linear systems

    Kei Kimura

    Kei Kimura and Akira Suzuki, The 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), Singapore, Singapore  2020年4月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Trichotomy for the reconfiguration problem of integer linear systems

  • 整数計画における遷移問題の計算量

    木村慧

    木村慧, 鈴木顕, 日本応用数理学会 2020年度 年会, オンライン開催  2020年9月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 制約充足問題に対する充足可能性保存割当ての解析 招待

    木村慧

    人工知能学会 第113回人工知能基本問題研究会(SIG-FPAI), オンライン開催  2020年9月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • Quantaloidal approach to constraint satisfaction

    Soichiro Fujii

    Soichiro Fujii, Yuni Iwamasa, and Kei Kimura, The 4th International Conference on Applied Category Theory, online  2021年7月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Quantaloidal approach to constraint satisfaction

  • マルチエージェント経路探索アルゴリズムの改良のための一検討

    柴田航志

    柴田航志，木村慧，東藤大樹，横尾真, SMASH(Symposium on Multi Agent Systems for Harmonization)22 Winter Symposium, オンライン  2022年2月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 多項式時間可解なHorn ILS及びTVPI ILSにおける遷移問題の拡張に関する研究

    重信 賢直

    重信 賢直, 神⼭ 直之, ⽊村 慧, 科研費・学術変⾰領域研究(B)「組合せ遷移の展開に向けた計算機科学・⼯学・数学によるアプローチの融合」, 組合せ遷移の学⽣シンポジウム, オンライン  2022年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • ぷよを自由に配置できるぷよぷよの連鎖数判定問題: 色数制限を課した場合

    澁谷諒祐

    澁谷諒祐, 木村慧, 組合せゲーム・パズル(CGP)プロジェクト 第16回研究集会, オンライン  2022年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • Neighborhood persistency of the linear optimization relaxation of integer linear optimization

    Kei Kimura

    Kei Kimura and Kotaro Nakayama, The 7th International Symposium on Combinatorial Optimization (ISCO), online  2022年5月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Neighborhood persistency of the linear optimization relaxation of integer linear optimization

  • 整数最適化の線形緩和における近傍永続性

    木村慧

    木村慧, 中山鼓太郎, 日本応用数理学会 2022年度 年会, オンライン開催  2022年9月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 遷移可能性制約をもつ彩色遷移問題 招待

    木村慧

    学術変革(B)「組合せ遷移」セミナー・勉強会  2022年10月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 一次元線分上の施設配置メカニズムの戦略的操作不可能性の緩和

    吉田健人

    吉田健人, 木村慧, 横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2023 WINTER SYMPOSIUM, 名古屋工業大学 + オンライン  2023年2月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 整凸関数におけるL拡張可能性

    横山健

    横山健，木村慧，横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2023 WINTER SYMPOSIUM, 名古屋工業大学 + オンライン  2023年2月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • Algorithms for coloring reconfiguration under recolorability digraphs

    Yuni Iwamasa

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura, and Akira Suzuki, The 33rd International Symposium on Algorithms and Computation (ISAAC), Seoul, Korea  2022年12月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    Algorithms for coloring reconfiguration under recolorability digraphs

  • マルチエージェント経路探索のための厳密アルゴリズムの改良

    柴田 航志

    柴田 航志, 木村 慧, 東藤 大樹, 横尾 真, 人工知能学会全国大会, 京都国際会館＋オンライン  2022年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 2期間マッチングにおける公平性と非浪費性

    米谷颯人

    米谷颯人, 木村慧, 孫兆鴻, 横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2024 WINTER SYMPOSIUM, 名古屋工業大学  2024年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • ソーシャルネットワーク上での両方向マッチングにおける公平性の緩和

    竹島遼太

    竹島遼太, 木村慧, 横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2024 WINTER SYMPOSIUM, 名古屋工業大学  2024年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 両方向マッチングにおける公平性の新たな緩和

    若杉天真

    若杉天真, 木村慧, 孫兆鴻, 横尾真, SMASH (Symposium on Multi Agent Systems for Harmonization) 2024 WINTER SYMPOSIUM, 名古屋工業大学  2024年2月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 整凸関数の線形補間による L 拡張可能性に関する一考察

    横山 健

    横山健, 岩政勇仁, 木村慧 横尾真, 日本応用数理学会第20回研究部会連合発表会, 長岡技術科学大学  2024年3月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems

    Kei Kimura

    Kei Kimura and Kazuhisa Makino, The 34th International Symposium on Algorithms and Computation (ISAAC), Kyoto, Japan  2023年12月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

    A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems

  • ヘドニックゲームにおけるナッシュ安定性と情報拡散のインセンティブの両立性分析

    赤星 雄太

    赤星 雄太, 木村 慧, 東藤 大樹, 横尾 真, 人工知能学会全国大会, 熊本城ホール + オンライン  2023年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 一次元区間上の施設配置メカニズムの戦略的操作の考察

    吉田 健人

    吉田 健人, 木村 慧, 横尾 真, 人工知能学会全国大会, 熊本城ホール + オンライン  2023年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

  • 整凸関数におけるL拡張可能性に関する一考察

    横山 健

    横山 健, 木村 慧, 横尾 真, 人工知能学会全国大会, 熊本城ホール + オンライン  2023年6月 

    　詳細を見る

    記述言語：その他  

    国名：その他  

▼全件表示

MISC

  • Optimal Matroid Partitioning Problems 査読

    Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita

    CoRR   2017年10月

    　詳細を見る

    記述言語：その他  

    Optimal Matroid Partitioning Problems

  • 制約充足問題に対する充足可能性保存割当ての解析とそのアルゴリズム設計への応用

    木村慧

    博士論文, 東京大学, 情報理工学系研究科   2015年3月

    　詳細を見る

    記述言語：その他  

  • q-Horn システムに対する組合せ的アルゴリズム

    木村慧

    修士論文, 東京大学, 情報理工学系研究科   2011年3月

    　詳細を見る

    記述言語：その他  

  • 行列の同時ブロック対角化：複素数上の分解と実数上の分解

    木村慧

    卒業論文, 東京大学, 工学部   2009年3月

    　詳細を見る

    記述言語：その他  

所属学協会

  • 電子情報通信学会

  • 日本オペレーションズ・リサーチ学会

共同研究・競争的資金等の研究課題

  • 制約充足問題の遷移問題に対する普遍代数学を用いたアプローチ

    研究課題/領域番号：21K17700  2021年 - 2025年

    日本学術振興会  科学研究費助成事業  若手研究

    　 詳細を見る

    資金種別：科研費

  • 演算不変性を用いた整数計画問題のアルゴリズム開発

    2020年 - 2022年

    戦略的創造研究推進事業 (文部科学省)

    　 詳細を見る

    担当区分：研究代表者  資金種別：受託研究

  • 局所構造を利用した高速なアルゴリズムの開発

    研究課題/領域番号：19K22841  2019年 - 2023年

    日本学術振興会  科学研究費助成事業  挑戦的研究（萌芽）

    　 詳細を見る

    担当区分：研究分担者  資金種別：科研費

  • The 14th International Conference and Workshop on Algorithms and Computation に参加し論文発表を行う

    2019年

    海外渡航旅費援助

    　 詳細を見る

    担当区分：研究代表者  資金種別：受託研究

  • The 27th International Joint Conference on Arti cial Intelligence に参加し論文発表を行う

    2018年

    研究者海外派遣助成

    　 詳細を見る

    担当区分：研究代表者  資金種別：受託研究

  • 整数計画問題に対するアルゴリズム開発

    2018年

    平成３０年度教育研究活性化経費（若手研究）

    　 詳細を見る

    担当区分：研究代表者  資金種別：学内資金・基金等

  • 離散構造をもつ判定問題への連続最適化手法の構築

    研究課題/領域番号：15H06286  2015年 - 2016年

    日本学術振興会  科学研究費助成事業  研究活動スタート支援

    　 詳細を見る

    資金種別：科研費

  • 制約充足問題に対する数理計画法を用いたアプローチ

    2013年 - 2014年

    日本学術振興会  特別研究員

    　 詳細を見る

    資金種別：共同研究

▼全件表示

担当授業科目

  • データ構造とアルゴリズムⅣ

    2024年6月 - 2024年8月   夏学期

  • データ構造とアルゴリズムⅡＢ

    2024年6月 - 2024年8月   夏学期

  • 【通年】情報理工学研究Ⅰ

    2024年4月 - 2025年3月   通年

  • 【通年】情報理工学講究

    2024年4月 - 2025年3月   通年

  • 【通年】情報理工学演習

    2024年4月 - 2025年3月   通年

  • 情報理工学読解

    2024年4月 - 2024年9月   前期

  • 情報理工学論議Ⅰ

    2024年4月 - 2024年9月   前期

  • 情報理工学論述Ⅰ

    2024年4月 - 2024年9月   前期

  • データ構造とアルゴリズムⅢ

    2024年4月 - 2024年6月   春学期

  • データ構造とアルゴリズムⅡＡ

    2024年4月 - 2024年6月   春学期

  • (IUPE)Data Structure and Algorithms IB

    2023年12月 - 2024年2月   冬学期

  • Evidence-based Policy Making II

    2023年12月 - 2024年2月   冬学期

  • データに基づく政策決定特論Ⅱ

    2023年12月 - 2024年2月   冬学期

  • 情報理工学演示

    2023年10月 - 2024年3月   後期

  • 情報理工学論議Ⅱ

    2023年10月 - 2024年3月   後期

  • 情報理工学論述Ⅱ

    2023年10月 - 2024年3月   後期

  • (IUPE)Data Structure and Algorithms IA

    2023年10月 - 2023年12月   秋学期

  • Evidence-based Policy Making I

    2023年10月 - 2023年12月   秋学期

  • データに基づく政策決定特論Ⅰ

    2023年10月 - 2023年12月   秋学期

  • 【通年】情報理工学研究Ⅰ

    2023年4月 - 2024年3月   通年

  • 数学創発モデリング

    2023年4月 - 2024年3月   通年

  • 【通年】情報理工学講究

    2023年4月 - 2024年3月   通年

  • 【通年】情報理工学演習

    2023年4月 - 2024年3月   通年

  • 情報理工学読解

    2023年4月 - 2023年9月   前期

  • 情報理工学論議Ⅰ

    2023年4月 - 2023年9月   前期

  • 情報理工学論述Ⅰ

    2023年4月 - 2023年9月   前期

  • (IUPE)Data Structure and Algorithms IB

    2022年12月 - 2023年2月   冬学期

  • データに基づく政策決定特論Ⅱ

    2022年12月 - 2023年2月   冬学期

  • プログラミング技法

    2022年10月 - 2023年3月   後期

  • 情報理工学論議Ⅱ

    2022年10月 - 2023年3月   後期

  • 情報理工学論述Ⅱ

    2022年10月 - 2023年3月   後期

  • 情報理工学演示

    2022年10月 - 2023年3月   後期

  • プログラミング技法

    2022年10月 - 2023年3月   後期

  • 電気情報工学実験II,III(2022後期)

    2022年10月 - 2023年3月   後期

  • 物理学入門IIB(2022後期オムニバス)

    2022年10月 - 2023年3月   後期

  • (IUPE)Data Structure and Algorithms IA

    2022年10月 - 2022年12月   秋学期

  • データに基づく政策決定特論Ⅰ

    2022年10月 - 2022年12月   秋学期

  • 情報理工学講究

    2022年4月 - 2023年3月   通年

  • 情報理工学演習

    2022年4月 - 2023年3月   通年

  • 情報理工学研究Ⅰ

    2022年4月 - 2023年3月   通年

  • 数学共創モデリング

    2022年4月 - 2023年3月   通年

  • 数学共創概論I

    2022年4月 - 2022年9月   前期

  • 情報理工学論議Ⅰ

    2022年4月 - 2022年9月   前期

  • 情報理工学論述Ⅰ

    2022年4月 - 2022年9月   前期

  • 情報理工学読解

    2022年4月 - 2022年9月   前期

  • Data Structure and Algorithms IA,IB

    2022年4月 - 2022年9月   前期

  • データに基づく政策決定特論I,II

    2022年4月 - 2022年9月   前期

  • 国際科学特論II(2021後期オムニバス)

    2021年10月 - 2022年3月   後期

  • 電気情報工学実験II,III

    2021年10月 - 2022年3月   後期

  • 国際科学特論Ⅱ

    2021年10月 - 2021年12月   秋学期

▼全件表示

FD参加状況

  • 2023年3月   役割：参加   名称：【シス情FD】独・蘭・台湾での産学連携を垣間見る-Industy 4.0・量子コンピューティング・先端半導体-

    主催組織：部局

  • 2023年1月   役割：参加   名称：【シス情FD】若手教員による研究紹介⑦

    主催組織：部局

  • 2022年10月   役割：参加   名称：【シス情FD】若手教員による研究紹介⑥

    主催組織：部局

  • 2022年9月   役割：参加   名称：【シス情FD】研究機器の共用に向けて

    主催組織：部局

  • 2022年7月   役割：参加   名称：【シス情FD】若手教員による研究紹介⑤

    主催組織：部局

  • 2022年6月   役割：参加   名称：【シス情FD】電子ジャーナル等の今後について

    主催組織：部局

  • 2022年5月   役割：参加   名称：【シス情FD】若手教員による研究紹介④「量子コンピュータ・システム・アーキテクチャの研究～道具になることを目指して～」

    主催組織：部局

  • 2022年4月   役割：参加   名称：令和４年度 第１回全学ＦＤ（新任教員の研修）The 1st All-University FD (training for new faculty members) in FY2022

    主催組織：全学

  • 2022年4月   役割：参加   名称：【シス情FD】第4期中期目標・中期計画等について

    主催組織：部局

  • 2022年3月   役割：参加   名称：全学FD:メンタルヘルス講演会

    主催組織：全学

  • 2022年1月   役割：参加   名称：【シス情FD】シス情関連の科学技術に対する国の政策動向（に関する私見）

    主催組織：部局

  • 2021年12月   役割：参加   名称：【シス情FD】企業出身教員から見た大学

    主催組織：部局

  • 2021年11月   役割：参加   名称：【シス情FD】若手教員による研究紹介　及び　研究費獲得のポイント等について③

    主催組織：部局

  • 2021年10月   役割：参加   名称：【シス情FD】熊本高専と九大システム情報との交流・連携に向けて ー 3年半で感じた高専の実像 ー

    主催組織：部局

▼全件表示

その他教育活動及び特記事項

  • 2023年  クラス担任  学部

  • 2022年  クラス担任  学部

社会貢献活動

  • 人工知能によるスケジュール作成を学ぼう

    埼玉大学  2021年8月

    　詳細を見る

    対象： 幼稚園以下,　小学生,　中学生,　高校生

  • 整数計画法によるパズル解法

    2018年

    　詳細を見る

    整数計画法によるパズル解法

  • 整数計画法によるパズル解法

    2017年

    　詳細を見る

    整数計画法によるパズル解法

  • 整数計画法によるパズル解法

    2016年

    　詳細を見る

    整数計画法によるパズル解法

メディア報道

  • 計算機（コンピュータ）により解ける問題、解けない問題

    FMラジオ広報「天伯之城 ギカダイ」  2018年2月

    　詳細を見る

    計算機（コンピュータ）により解ける問題、解けない問題

政策形成、学術振興等への寄与活動

  • 2021年6月 - 2023年6月   電子情報通信学会コンピュテーション研究会

    専門委員

  • 2019年7月 - 2023年9月   電子情報通信学会

    英文論文誌小特集編集委員会 編集委員

  • 2018年8月 - 2019年9月   電子情報通信学会

    英文論文誌小特集編集委員会 編集委員

  • 2017年5月 - 2021年5月   電子情報通信学会

    Associate Editor of IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  • 2017年5月 - 2021年5月   電子情報通信学会

    基礎・境界ソサイエティ和文論文誌編集委員

  • 2016年5月 - 2018年5月   日本オペレーションズ・リサーチ学会

    論文誌編集幹事

  •   The 11th International Conference on Fun with Algorithms (FUN 2022)

    Program Commitee

  •   The 6th International Congress on Advanced Applied Informatics (AAI 2017)

    Program Commitee

  •   The 2017 International Conference on Advanced Informatics: Concept Theory and Applications (ICAICTA)

    Program Commitee

  •   2016, 2017, 2018, 2019年 幹事, 2020年 研究提案者

    RIMS 共同研究「組合せ最適化セミナー」

▼全件表示

学内運営に関わる各種委員・役職等

  • 2024年4月 - 2026年3月   その他 九州支部幹事

  • 2023年4月 - 2024年3月   部門 安全衛生委員

  • 2022年4月 - 2023年3月   部門 情報通信委員

  • その他 Program Committee

  • その他 Program Committee