学位

• 博士(工学)（京都大学）

経歴

学歴

受賞

その他

論文

• Solvability of Peg Solitaire on Graphs is NP-Complete（2023-06-01） [DOI] [Othres link]
• On the Power of Lookahead in Single-Player PuyoPuyo（2021）
• QUIXO is EXPTIME-complete（2020-10）
• Matchstick Puzzles on a Grid（2020-03）
• Anti-Slide Placements of Pentominoes（2019-09-07）
• Matchstick Puzzles on a Grid（2017-08）
• Strategies for Single-Player PuyoPuyo（2017） [DOI] [Web of Scientce]
• Number of Three-Point Tilings with Triangle Tiles（2015） [DOI]
• Satogaeri, Hebi and Suraromu are NP-Complete（2015） [DOI] [Web of Scientce]
• Shikaku and Ripple Effect are NP-Complete（2013-12）
• NP-completeness of pandemic（2012） [DOI]
• Precoloring Extension on Grid Graphs（2010-10）
• STONEHENGE: OUTCOME OF ALL FIRST MOVES AND PSPACE-COMPLETENESS（2010-03） [Web of Scientce]
• PSPACE-completeness of an escape problem（2008-10） [DOI] [Web of Scientce]
• Tree-shellability of restricted DNFs（2008-04） [DOI] [Web of Scientce]
• Vertex Coloring of Chordal+k_1e-k_2e Graphs（2007-11）
• TETRAVEX is NP-complete（2006-09） [DOI] [Web of Scientce]
• 組合せ最適化問題としてのぷよぷよの連鎖数判定問題（2006-03） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• Vertex coloring of comparability +ke and -ke graphs（2006） [Web of Scientce]
• 一般化ぷよぷよのNP完全性（2005-04） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link] [Othres link]
• 比較可能+keグラフの彩色問題（2005-04） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link] [Othres link]
• 積項の長さに制限を付けた論理関数のOrdered Tree-Shellability（2004-05） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link] [Othres link]
• Tree-shellability of Boolean functions（2001-07） [Web of Scientce]
• Tree-Shellable論理関数の判定の複雑さ(共著)（2001-05） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link] [Othres link]
• Recognition of ordered tree-shellable Boolean functions based on OBDDs（2001-01） [Web of Scientce]
• Hardness of Identifying the Minimum Ordered Binary Decision Diagram(共著)（2000-12） [Web of Scientce]
• Size of ordered binary decision diagrams representing threshold functions(共著)（1997-07） [CiNii Research (CiNii Articles)]
• Computational Power of Nondeterministic Ordered Binary Decision Diagrams and Their Subclasses(共著)（1997-04） [Web of Scientce]
• Size and Variable Ordering of OBDDs Representing Threshold Functions(共著)（1997）
• On the Size of Ordered Binary Decision Diagrams Representing Threshold Functions(共著)（1994-08） [CiNii Research (CiNii Articles)]
• On the Computational Power of Binary Decision Diagrams(共著)（1994-06） [Web of Scientce]
• Computational Complexity of Manipulating Binary Decision Diagrams(共著)（1994-06） [Web of Scientce]
• 連想メモリによるメモリ型並列計算モデルの計算能力(共著)（1992-04） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• Computational Power of Memory-Based Parallel Computation Models with Communication(共著)（1992-01） [Web of Scientce]
• メモリ型並列計算モデルとその計算能力(共著)（1990-11）

その他業績

講演・口頭発表等

• ヤバラスのPSPACE完全性（2025-03-14）
• 色数1の一般化ぷよぷよの連鎖数判定問題（2025-03-14）
• 一人用ダイヤモンドゲームにおける最小手数について（2024-03-07）
• 様々なグラフ上での「うさぎと猟犬」の必勝性について（2024-03-07）
• Approximate Block Diagonalization of Symmetric Matrices Using Quantum Annealing（2024-01-16）
• 泥棒の速度が異なるCops and Robbersの格子上における戦略（2023-03-07）
• Finding a Shortest Solution for Single-Player Chinese Checkers is NP-complete（2022-03-17）
• 三人一般化七並べの必勝性（2022-03-15）
• ペントミノを用いたアンチスライドパズルの解の列挙（2022-03-15）
• グラフ上のダイヤモンドゲームの計算複雑さ（2022-03-15）
• NP-completeness of peg solitaire on graphs（2021-09-04）
• 二人一般化七並べの戦略（2020-03-17）
• グラフ上のペグソリティアの計算困難性（2020-03-17）
• 先読みを考慮した一人ぷよぷよの必勝性（2020-03-05）
• Anti-Slide Placements of Pentominoes（2019-09-07）
• 幅３色数３の一人ぷよぷよの必勝性（2019-03-19）
• 格子上での Cops and Robbers の方向のみ認知可能なルール（2019-03-19）
• ペントミノを用いたアンチスライドパズルの解の列挙（2019-03-15）
• On Winning Strategies for Tetris Type Games（2017-08-25）
• 先読みありの1人ぷよぷよの必勝性（2017-03-22）
• 一般化QUIXOの計算複雑さ（2017-03-22）
• 一人用落ち物パズルゲームの必勝性（2017-03-22）
• グラフ上の一般化ペグソリティア（2017-03-22）
• 格子上のマッチ棒パズル（2017-03-06）
• 木+keグラフの部分グラフ同型判定アルゴリズム（2014-03-19）
• フロンティア法を用いた根無し木の列挙（2014-03-19）
• 色数と盤面の幅を限定したぷよぷよの必勝性（2014-02-28）
• 比較可能-keグラフの頂点彩色問題のパラメータ化計算量（共著）（2012-03）
• パラメータ化permutationグラフの頂点彩色問題（2012-03）
• 木+keグラフの同型性判定問題（2012-03）
• パラメータ化グラフに対するFixed-Parameterアルゴリズムの設計手法（2010-03）
• ナンバーリンクのＮＰ完全性と問題の列挙（2010-03）
• 多変量閾値関数の非明示的OBDD表現（2008-03）
• OBDDを用いた画像処理アルゴリズム（2008-03）
• Chordal+k_1e-k_2eグラフの頂点彩色問題（2007-03）
• 種々の制限を加えたTree-Shellable論理関数判定問題の計算複雑さ（2006-03）
• Coloring Comparability-ke Graphs（2006-02）
• リテラルの出現回数に制限を加えたTree-Shellable論理関数の判定複雑さ（2005-05）
• 区間グラフのOBDD表現について（2005-03）
• ブロック化分岐プログラムにおける変数順序と表現能力の関係（2004-03）
• 変数の出現回数が制限されたBranching Programの表現能力(共著)（2002-01）
• Complexity of Recognizing Tree-Shellable Functions（2001-11）
• Recognition of Tree-Shellable Boolean Functions（2001-07）
• Tree-Shellable論理関数の判定の複雑さ(共著)（2001-01）
• 幅に制限を加えたOBDDの等価性判定(共著)（2000-11）
• Checking ordered tree-shellability of boolean function based on OBDDs（1999-10）

書籍等出版物

• プレパラータ先生の超並列計算講義（共編・訳）（1996）

作品等

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

メディア報道

産業財産権

所属学協会

• 電子情報通信学会
• 情報処理学会

委員歴

担当経験のある科目

• グラフとネットワーク
• 計算機数学
• 応用解析

社会貢献活動

学術貢献活動

• 26th Workshop on Advances in Parallel and Distributed Computational Models (APCDM2024)
• The Twelfth International Symposium on Computing and Networking
• The Eleventh International Symposium on Computing and Networking (CANDAR2023)
• 25th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2023)
• 情報処理学会 第85回全国大会
• The 9th International Symposium on Computing and Networking (CANDAR2021)
• 23rd Workshop on Advances in Parallel and Distributed Computational Models (APDCM2021)
• 22nd Workshop on Advances in Parallel and Distributed Computational Models (APDCM2020)
• The Eighth International Symposium on Computing and Networking (CANDAR2020)
• 21st Workshop on Advances in Parallel and Distributed Computational Models (APDCM2019)
• 20th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2018)
• The Sixth International Symposium on Computing and Networking (CANDAR2018)
• 19th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2017)
• The Fifth International Symposium on Computing and Networking (CANDAR2017)
• 18th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2016)
• 17th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2015)
• 14th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP2014)
• 16th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2014)
• 11th IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA13)
• 15th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2013)
• 14th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2012)
• 13th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2011)
• 3rd International Workshop on Parallel and Distributed Algorithms and Applications (PDAA)
• 2nd International Workshop on Parallel and Distributed Algorithms and Applications (PDAA10)
• 12th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2010)
• 11th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2009)
• 10th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2008)
• 9th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2007)
• 8th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2006)
• 7th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2005)
• 6th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2004)
• 5th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2003)
• 4th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2002)
• 3rd Workshop on Advances in Parallel and Distributed Computational Models (APDCM2001)