学位

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

経歴

学歴

受賞

その他

論文

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

その他業績

講演・口頭発表等

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

書籍等出版物

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

作品等

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

• パラメータや盤面を変更したゲームの必勝戦略と計算複雑さ
• 組合せ的前処理と量子アニーリングの融合による行列計算の加速手法
• グラフ上のゲームおよびオンライン性を持つゲームの必勝性
• ゲーム・パズルにおけるオンライン問題と計算複雑さ
• ゲーム情報学：Ａｎｄ－Ｏｒ木の探索とゲーム・パズルの難しさの研究
• パラメータ化グラフアルゴリズムの研究
• 論理関数表現のモデルとシンボリックアルゴリズム
• 形式言語理論の自然言語処理への応用
• 計算機科学における下界の研究
• 論理関数のグラフ表現の性質と双対比への応用
• マイクロプロセッサの形式的論理設計検証システムの試作研究
• 論理関数高速処理機構に関する基礎的研究
• 時相理論に基づく論理設計の形式的検証システムの試作研究
• 二分決定グラフの性質と並列処理アルゴリズムに関する研究
• 論理関数処理の並列アルゴリズムと計算複雑さに関する研究
• ブール関数処理による順序回路の自動合成・設計検証システムの試作研究
• 共有二分決定図による論理関数の効率的処理とそれに基づく論理設計支援に関する研究

メディア報道

産業財産権

所属学協会

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

委員歴

担当経験のある科目

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

社会貢献活動

学術貢献活動

• 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)