2025/10/30 更新

写真a

クリタ　カズヒロ
栗田　和宏
Kazuhiro Kurita
所属
環境生命自然科学学域 准教授
職名
准教授
外部リンク

学位

  • 博士（情報科学） （ 2020年3月   北海道大学 ）

研究キーワード

  • 最適化

  • アルゴリズム

  • トップ-K/K-ベスト列挙

  • 列挙

学歴

  • 北海道大学   Graduate School of Information Science and Technology  

    2017年4月 - 2020年3月

    　 詳細を見る

    国名： 日本国

    researchmap

経歴

  • 岡山大学   大学院環境生命自然科学学域   准教授

    2025年10月 - 現在

    　 詳細を見る

    国名：日本国

    researchmap

  • 名古屋大学   大学院情報学研究科   助教

    2022年7月 - 2025年9月

    　 詳細を見る

    国名：日本国

    researchmap

  • 国立情報学研究所   情報学研究プリンシプル系   特任研究員

    2020年4月 - 2022年6月

    　 詳細を見る

    国名：日本国

    researchmap

  • 独立行政法人日本学術振興会   特別研究員

    2019年4月 - 2021年3月

    　 詳細を見る

    国名：日本国

    researchmap

所属学協会

  • 一般社団法人人工知能学会

    2021年6月 - 現在

    　 詳細を見る

  • 一般社団法人情報処理学会

    2020年5月 - 現在

    　 詳細を見る

 

論文

▼全件表示

MISC

  • 出力依存型DD構築の計算複雑性

    栗田和宏

    列挙アルゴリズムセミナー   2025年8月

    　詳細を見る

    担当区分：筆頭著者  

    researchmap

  • ⾼さ2の根付き⽊に対する頻出飽和部分⽊の多項式遅延列挙

    甲本健太, 栗田和宏, 小野廣隆

    2025年度夏のLAシンポジウム   2025年7月

    　詳細を見る

  • ラベル付き木に対する極大頻出誘導部分木マイニングの計算複雑性

    甲本健太, 栗田和宏, 小野廣隆

    2025年3月

    　詳細を見る

  • 有向ハイパーグラフ上のパスと極小頂点カットの列挙

    栗田和宏, ケビンマン

    2024年度冬のLAシンポジウム   2025年1月

    　詳細を見る

    担当区分：筆頭著者  

    researchmap

  • Maximal Common Subsequence Enumeration is Hard

    Giovanni Buzzega, Alessio Conte, Yasuaki Kobayashi, ○Kazuhiro Kurita, Giulia Punzi

    第131回人工知能基本問題研究会   2025年1月

    　詳細を見る

    担当区分：筆頭著者  

    researchmap

  • Finding distinct 2-maximal independent sets is hard

    Yasuaki Kobayashi, Kazuhiro Kurita

    2024年度冬のLAシンポジウム   2025年1月

    　詳細を見る

  • コード類似を利用した楽曲の自然な変容

    松下 昂世, 栗田 和宏, 小野 廣隆

    2024年度冬のLAシンポジウム   2025年1月

    　詳細を見る

  • 重み制約付き極大マッチングの多項式遅延列挙

    小林靖明, 栗田和宏, 和佐州洋

    列挙アルゴリズムセミナー   2024年8月

    　詳細を見る

    担当区分：筆頭著者  

    researchmap

  • Computing diverse pair of solutions for SAT

    儀間達也, 岩政勇仁, 小林靖明, 栗田和宏, 大舘陽太, 斉藤凜

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

    　詳細を見る

    記述言語：英語   掲載種別：研究発表ペーパー・要旨（全国大会，その他学術会議）  

    researchmap

  • Computing diverse pair of solutions for SAT

    儀間達也, 岩政勇仁, 小林靖明, 栗田和宏, 大舘 陽太, 斉藤凜

    2023年度冬のLAシンポジウム   2024年2月

    　詳細を見る

    記述言語：英語   掲載種別：研究発表ペーパー・要旨（全国大会，その他学術会議）  

    researchmap

  • An Edit Model and Algorithms for Achieving Properties on Intersection Graphs

    オノラト ドロゲット ニコラス, 栗田 和宏, 土中 哲秀, 小野 廣隆

    2023年度冬のLAシンポジウム   2024年2月

    　詳細を見る

    記述言語：英語  

    researchmap

  • 極小シュタイナー多点対頂点カット列挙の計算困難性

    小林 靖明, 栗田 和宏

    2023年度冬のLAシンポジウム   2024年

    　詳細を見る

    担当区分：筆頭著者   記述言語：日本語   掲載種別：研究発表ペーパー・要旨（全国大会，その他学術会議）  

    researchmap

  • Algorithms for Optimally Shifting Intervals under Intersection Graph Models

    Nicolás Honorato Drogue, Kazuhiro Kurita, Tesshu Hanaka, Hirotaka Ono

    日本オペレーションズ・リサーチ学会 九州支部 九州地区におけるOR若手研究交流会   2023年10月

    　詳細を見る

    記述言語：英語   掲載種別：研究発表ペーパー・要旨（全国大会，その他学術会議）  

    researchmap

  • 最適 LZ-End 分解

    坂内 英夫, 舩越 満, 栗田 和宏, 中島 祐人, 脊戸 和寿, 宇野 毅明

    2022年度冬のLAシンポジウム   2023年2月

    　詳細を見る

  • 弦グラフの部分クラスにおける極大誘導部分グラフ列挙への多項式遅延アルゴリズム

    佐藤嶺, 小林靖明, 栗田和宏, 和佐州洋

    電子情報通信学会技術研究報告(Web)   123 ( 325(COMP2023 16-27) )   2023年

    　詳細を見る

  • 最大最小k-パス頂点被覆問題

    HANAKA Tesshu, KOBAYASHI Yasuaki, KURITA Kazuhiro

    情報処理学会研究報告(Web)   2023 ( AL-192 )   2023年

    　詳細を見る

  • 交差グラフモデルの下での最適シフト区間のためのアルゴリズム【JST・京大機械翻訳】|||

    HONORATO DROGUETT Nicolas, KURITA Kazuhiro, HANAKA Tesshu, ONO Hirotaka

    電子情報通信学会技術研究報告(Web)   123 ( 325(COMP2023 16-27) )   2023年

    　詳細を見る

  • 要素数制約付き極大マトロイド共通独立集合の多項式遅延列挙

    小林靖明, 栗田和宏, 和佐州洋

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

    　詳細を見る

  • Wikipediaの影響関係データを用いた20世紀フランス思想家ネットワークの分析

    須田, 永遠, 前山, 和喜, 武富, 有香, 杉山, 佳奈美, 栗田, 和宏, 宇野, 毅明

    じんもんこん2022論文集   2022   193 - 198   2022年12月

    　詳細を見る

    記述言語：日本語  

    思想家・作家の認識や問題設定の前提には，周囲の人物やコミュニティとのつながりが大きく関わっており，その創作活動と切り離すことはできない．しかしながら，従来の思想・文学研究では，人と人とのつながりやコミュニティの大局的な構造を扱うことが難しい．本研究ではWikipedia のエントリ内に記載された影響関係の情報から20 世紀フランス思想家のネットワークを作成した．そのネットワークを対象とし，次数中心性，媒介中心性，近接中心性，固有ベクトル中心性を算出した．数理的に解析したものを思想・文学研究の知見から検討した結果，既存の思想史研究の見解に一致するものがみられた．
    The creative activities of philosophers and writers are deeply connected to the people and communities around them. However, for conventional studies of the history of ideas and literature, it is difficult to treat the characteristics of the complicated connections of people. We created a network of 20th-century philosophers based on the information on influence relations described in Wikipedia entries. Then each centrality was calculated: degree centrality, betweenness centrality, closeness centrality, and eigenvector centrality. The results are consistent with existing research on the history of ideas.

    researchmap

  • 平面グラフ中の辺連結度制約付き全域部分グラフの効率良い列挙

    小林靖明, 栗田和宏, 和佐州洋

    電子情報通信学会 コンピュテーション研究会   2022年10月

    　詳細を見る

    担当区分：筆頭著者   掲載種別：研究発表ペーパー・要旨（全国大会，その他学術会議）  

    researchmap

  • 平面グラフ中の極小全域2辺連結部分グラフの多項式遅延列挙

    小林靖明, 栗田和宏, 和佐州洋

    情報処理学会 第84回全国大会 革新的アルゴリズム基盤の構築に向けて   2022年3月

    　詳細を見る

    担当区分：筆頭著者  

    researchmap

  • Collecting Balls on a Line by Robots with Limited Energy

    2022年度冬のLAシンポジウム   107 ( 3 )   325 - 327   2022年2月

    　詳細を見る

  • 多様な解集合を発見する効率良い近似アルゴリズム

    栗田 和宏, 土中 哲秀, 清見 礼, 小林 靖明, 小林 佑輔, 大舘 陽太

    人工知能学会研究会資料 人工知能基本問題研究会   119   21 - 26   2022年

    　詳細を見る

    記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

    DOI： 10.11517/jsaifpai.119.0_21

    CiNii Article

    CiNii Books

    researchmap

  • 省メモリなトップk列挙アルゴリズムの設計技法

    KOBAYASHI Yasuaki, KURITA Kazuhiro

    人工知能学会人工知能基本問題研究会資料   117th   2021年

    　詳細を見る

  • 多様な部分グラフを発見するアルゴリズム

    HAKANA Tesshu, KOBAYASHI Yasuaki, KURITA Kazuhiro, OTACHI Yota

    人工知能学会人工知能基本問題研究会資料   113th   2020年

    　詳細を見る

  • Subgraph Enumeration: Efficient Algorithms and Empirical Studies 国際誌

    Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura

    The 2nd International Workshop on Enumeration Problems & Application   2018年11月

    　詳細を見る

    記述言語：英語   掲載種別：研究発表ペーパー・要旨（国際会議）  

    researchmap

  • Efficient Enumeration Algorithm for Dominating Sets in Bounded Degenerate Graphs (アルゴリズムと計算理論の基礎と応用)

    Kurita Kazuhiro, Wasa Kunihiro, Arimura Hiroki, Uno Takeaki

    数理解析研究所講究録   ( 2088 )   44 - 52   2018年8月

    　詳細を見る

    記述言語：英語   出版者・発行元：京都大学数理解析研究所  

    Dominating sets are fundamental graph structures. However, enumeration of dominating sets has not received much attention. This study aims to propose an efficient enumeration algorithms for bounded degenerate graphs. The algorithm enumerates all the dominating sets for k-degenerate graphs in O(k) time per solution using O(n+m) space. Since planar graphs have a constant degeneracy, this algorithm can enumerate all such sets for planar graphs in constant time per solution.

    CiNii Article

    CiNii Books

    researchmap

    その他リンク： http://hdl.handle.net/2433/251597

  • グラフに含まれる大きな内周を持つ部分グラフの効率良い列挙

    栗田 和宏, Alessio Conte, 和佐 州洋, 宇野 毅明, 有村 博紀

    第80回全国大会講演論文集   2018 ( 1 )   347 - 348   2018年3月

    　詳細を見る

    記述言語：日本語  

    内周はグラフに含まれる最小の閉路長を表し,グラフの内周を計算する問題はよく研究されている.ItaiとRodehは一般グラフの内周を計算する非自明な最初のアルゴリズムを開発した.このアルゴリズムは最悪時O(nm)時間で動作し,平均時間O(n^2)時間で動作する.重みなし平面グラフに対しては,DjidjevがO(n^{5/4} log n)時間アルゴリズムを与え,Changらがこのアルゴリズムを改良し線形時間アルゴリズムを与えた.我々の知る限りでは大きな内周を持つ連結な部分グラフを列挙するアルゴリズムは存在しない.本論文では,これらの問題を解く列挙アルゴリズムを与える.このアルゴリズムの単純な拡張により,k以上の内周を持つ重み付きグラフの部分グラフや非連結なグラフの列挙も可能である.

    CiNii Article

    CiNii Books

    researchmap

  • 決定化されたグラフパターントライの学習アルゴリズム (特集 「ビジネスにおける機械学習/人工知能」及び一般)

    坂上 陽規, 栗田 和宏, 瀧川 一学, 有村 博紀

    人工知能基本問題研究会   105   63 - 68   2018年1月

    　詳細を見る

    記述言語：日本語   出版者・発行元：人工知能学会  

    CiNii Article

    CiNii Books

    researchmap

  • 非同型な2端子直並列グラフの列挙とランダムサンプリング

    伝住周平, 堀山貴史, 栗田和宏, 中畑裕, 鈴木浩史, 和佐州洋, 山崎一明

    電子情報通信学会技術研究報告   118 ( 216(COMP2018 9-20)(Web) )   2018年

    　詳細を見る

  • Efficient Enumeration of Dominating Sets in k-degenerate Graphs (情報セキュリティ)

    栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   117 ( 369 )   111 - 117   2017年12月

    　詳細を見る

    記述言語：英語   出版者・発行元：電子情報通信学会  

    CiNii Article

    CiNii Books

    researchmap

  • Efficient Enumeration of Dominating Sets in k-degenerate Graphs (コンピュテーション)

    栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   117 ( 370 )   111 - 117   2017年12月

    　詳細を見る

    記述言語：英語   出版者・発行元：電子情報通信学会  

    CiNii Article

    CiNii Books

    researchmap

  • グラフに含まれる誘導マッチングの列挙

    栗田和宏, 和佐州洋, 喜田拓也, 有村博紀

    情報処理学会研究報告(Web)   2016 ( AL-157 )   2016年

    　詳細を見る

  • D-032 2次元軌跡データに対する高速なパターン照合アルゴリズム(D分野:データベース,一般論文)

    山本 雅大, 栗田 和宏, 笹川 裕人, 有村 博紀

    情報科学技術フォーラム講演論文集   13 ( 2 )   153 - 154   2014年8月

    　詳細を見る

    記述言語：日本語   出版者・発行元：FIT(電子情報通信学会・情報処理学会)運営委員会  

    CiNii Article

    CiNii Books

    researchmap

▼全件表示

受賞

  • 研究会優秀賞

    2020年6月   人工知能学会   多様な部分グラフを発見するアルゴリズム

    土中 哲秀, 小林 靖明, 栗田 和宏, 大舘 陽太

    　詳細を見る

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

  • 文字列に対するアルファベット順序最適化理論

    研究課題/領域番号：25K00136  2025年04月 - 2030年03月

    日本学術振興会  科学研究費助成事業  基盤研究(B)

    中島 祐人, 坂内 英夫, 栗田 和宏

    　 詳細を見る

    配分額：18720000円 （ 直接経費：14400000円 、 間接経費：4320000円 ）

    researchmap

  • 列挙の困難性に関する理論基盤構築

    研究課題/領域番号：25K03080  2025年04月 - 2030年03月

    日本学術振興会  科学研究費助成事業  基盤研究(B)

    和佐 州洋, 山中 克久, 栗田 和宏

    　 詳細を見る

    配分額：18720000円 （ 直接経費：14400000円 、 間接経費：4320000円 ）

    researchmap

  • 部分グラフ列挙問題に対する計算困難性の精緻化

    研究課題/領域番号：25K21273  2025年04月 - 2030年03月

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

    栗田 和宏

    　 詳細を見る

    配分額：4810000円 （ 直接経費：3700000円 、 間接経費：1110000円 ）

    researchmap

  • 文学的読解を通じた意図の推察に基づくSNS上の誹謗中傷・悪口の分析手法の開発

    研究課題/領域番号：24K15204  2024年04月 - 2029年03月

    日本学術振興会  科学研究費助成事業  基盤研究(C)

    武富有香, 杉山佳奈美, 須田永遠, 松田智裕, 栗田和宏

    　 詳細を見る

    配分額：4550000円 （ 直接経費：3500000円 、 間接経費：1050000円 ）

    researchmap

  • SNS解析のための日本語文体論の構築

    研究課題/領域番号：22K12285  2022年04月 - 2027年03月

    日本学術振興会  科学研究費助成事業 基盤研究(C)  基盤研究(C)

    須田 永遠, 栗田 和宏, 武富 有香

    　 詳細を見る

    配分額：4290000円 （ 直接経費：3300000円 、 間接経費：990000円 ）

    本年度は、ソーシャルメディアの書き手の反応や心的状態の類型および言語的特徴に関する知見を獲得するため、実際に国内で影響力のある二つのソーシャルメディアを対象としてテキストデータを収集し、分析を行った。並行して本研究に必要なマイニング技術を下支えするアルゴリズムの開発も行い、これらの成果を国内外の会議や論文誌で発表した。詳細は以下の通りである。
    (i) ワクチンに関する大規模なTwitterデータの分析：新型コロナウイルスワクチン接種期間中にTwitterで投稿された「ワクチン」の語を含む１億件以上の日本語の全ツイートデータを収集し、クラスタリング技術を用いてトピックごとに分類し、人手による意味解釈とアノテーションを施した上で時系列解析を行った。その結果、職域接種の開始を境に、人々の関心が社会的トピックから個人的事柄へと推移したことが明らかになった。
    (ii) Yahoo!コメント上の#metooに対する中傷の類型化とアノテーション：#metoo運動以降、Yahoo!コメントに現れるようになった女性に対する誹謗中傷的ナラティヴを人手で読解・精査し、類型を作成、その類型にしたがってコメントにアノテーションを行うことで性暴力トピックに対する書き手の典型的な反応を析出し、反応の分布を明らかにした。その結果の一部は従来のミソジニーに関する人文学的研究の知見を定量的に証明するものとなった。
    (iii) テキストマイニング技術の基礎となるアルゴリズムの開発：大量のテキストデータから書き手の心的状態と結びついた言語的特徴の累計を析出するには、まず限られたテキストを人手で解釈する必要があるが、その際にはある条件を満たす文を効率よくマイニングする情報学的な技術が必須である。こうした技術を下支えするアルゴリズム、本年度は特に条件をできるだけ満たす解（準最適解）を列挙するアルゴリズムの開発を行った。

    researchmap

  • 列挙や数え上げなどを統一的に扱うための基盤技術

    研究課題/領域番号：22H03549  2022年04月 - 2026年03月

    日本学術振興会  科学研究費助成事業 基盤研究(B)  基盤研究(B)

    堀山 貴史, 伝住 周平, 和佐 州洋, 栗田 和宏, 脊戸 和寿, 中畑 裕

    　 詳細を見る

    配分額：17160000円 （ 直接経費：13200000円 、 間接経費：3960000円 ）

    列挙、数え上げ、サンプリングなどのアルゴリズムは、互いに深く関連しつつも、それぞれ独自の技法が必要とされることが多い。ここで、同じ制約条件のもとで、つまり同じ解空間において、解の列挙、数え上げなどタイプの異なるアルゴリズムそれぞれを個別に設計する状況を見つめ直し、アルゴリズム設計者が頭の中に持つ解空間に関する理解をもとにアルゴリズムを導出する過程を明らかにすることで、列挙、数え上げ、サンプリングなどのアルゴリズム設計を統一的に扱うための指針を与えることを本研究課題の目的としている。
    本研究課題の研究者のみならず、課題外の連携研究者との議論も通して、列挙や数え上げなどのアルゴリズム設計の過程の再検討を行った。具体的には、たとえば、グラフの同型性の観点から代表元のみを列挙する同型性の除去について、ZDD (Zero-Suppressed Binary Decision Disgrams; 零抑制型二分決定グラフ) を用いるアプローチの検討を行った。制約条件を満たす解集合をうまく区分し、それらの区分された解集合相互の関係を表す方法を検討する際に、非同型なものを漏れなく重複なく求められる保証を与える必要があり、具体的なアルゴリズム設計を通して、アルゴリズム設計とアイデア記述に関する知見を得た。また、列挙と深い関連を持つ組合せ遷移問題も含めて、関連分野への応用に関する検討を行った。具体的には、たとえば、45度系格子パターン上での折り紙の展開図の列挙と数え上げの技法についてである。この問題では、縦横および斜め45度方向の格子上のみに折り線の位置を限定し、各頂点で平坦に折ることのできる局所平坦性を制約として、展開図の列挙または数え上げを行っている。また、格子の規則性から、回転および鏡映反転による同型性を考慮する必要があり、応用上の要請だけでなく、本研究課題の方向性にも沿った研究成果である。

    researchmap

  • 部分グラフ列挙問題で用いる多項式遅延列挙アルゴリズム設計技法の拡張に関する研究

    研究課題/領域番号：21H05861  2021年09月 - 2023年03月

    日本学術振興会  科学研究費助成事業 学術変革領域研究(A)  学術変革領域研究(A)

    栗田 和宏

    　 詳細を見る

    担当区分：研究代表者 

    配分額：2600000円 （ 直接経費：2000000円 、 間接経費：600000円 ）

    本年度は独立性システムに関する列挙問題とマトロイドに関する列挙問題の特殊系となるグラフの列挙問題について研究を行った．
    独立性システムの列挙に関しては k -拡張システムの極大解列挙アルゴリズムの構築に取り組んだ．これは定義から， k が定数であるならば多項式遅延で列挙できることがわかった．しかし，この結果の興味深い点は，多項式遅延列挙ができるが入力制約問題が多項式時間で解けるかがわかっていないという点である．そこで，次なる課題として，入力制約問題が多項式時間で解けるかを調べるために具体的な離散構造の列挙問題に取り組んだ．その問題として，マトロイドマッチングについて研究を行った．マトロイドマッチングは組合せ最適化分野で古くから知られる離散構造であり，二部グラフマッチングの一般化となっている．この問題は最適化問題としてはNP-困難であることが知られているが，列挙問題としてみた時，マトロイドマッチングの特殊系の問題は入力制約問題が多項式時間で解けることに気づいた．そこで，マトロイドマッチングについての列挙問題を研究したところ，マトロイドマッチングが2-拡張可能システムであることがわかった．この結果はグラフをハイパーグラフに拡張した場合，ハイパー辺のサイズが定数 k であればマトロイドマッチングは k-拡張可能システムになることがわかった．従って，この構造は多項式遅延で列挙できることがわかったが，まだ入力制約問題が多項式時間で解ける反例は得られなかった．
    次に，マトロイドに関連するグラフ上の列挙問題としてはグラフ中の極小な全域2辺連結部分グラフを列挙する問題について研究を行い，グラフが平面的である場合はこの問題は多項式遅延が可能であると予想する．これは平面グラフにおいて，辺連携性と最小サイクルが非常に深い関係があるため，その知見を用いた良いアルゴリズムが設計できるためである．

    researchmap

  • 大規模SNS上の話題の構造化による集合行動解析手法

    研究課題/領域番号：21H03559  2021年04月 - 2026年03月

    日本学術振興会  科学研究費助成事業 基盤研究(B)  基盤研究(B)

    橋本 隆子, 宇野 毅明, 栗田 和宏, 申 吉浩, 小林 亮太, 久保山 哲二

    　 詳細を見る

    配分額：16900000円 （ 直接経費：13000000円 、 間接経費：3900000円 ）

    1. Two-Stage Clustering 手法の開発
    2021年度は、SNSにおける人々の反応を分析するために、マイクロクラスタリングと時系列クラスタリングを組み合わせた Two-Stage Clustering 手法を提案し、コロナワクチンに対するTwitterデータ（全量データ）の分析を行った。この手法は、これまで内容の類似度に加えて、時系列上のパターン類似度を考慮できる効率的な手法であり、これにより、コロナワクチンに関する12M以上のTweet集合を、速報ニュースへの反応、Tweetへの反応、その他（デマなど）に分類できることを示した。結果を論文としてまとめ、BigData2021にも採択された。また招待講演等でも紹介を行った。
    ２. コロナワクチンに関する人々の反応評価（時系列分析）
    さらにTwitterの全量データを対象として、コロナワクチンに対する人々の反応のセンチメント分析（時系列評価）にも取り組んでおり、コロナワクチンに対する日本国民の気持ちが時間とともにどのような変遷をたどったかについて考察している。結果は、近日中に社会科学系のジャーナルに投稿予定である。
    3. マイクロクラスタリング手法の改良
    大規模データに対応可能とするために、マイクロクラスタリング手法を、より類似度の高いインスタンスを初期のタイミングで集約する改良を行った。これにより、数千万件規模のTwitterデータが標準的なPC上でリーズナブルな速度で分析可能となった。大規模データ分析において、極めて重要な成果であると認識している。

    researchmap

  • サイズ制約付き極小部分集合列挙問題に対する多項式遅延近似列挙アルゴリズムの研究

    研究課題/領域番号：21K17812  2021年04月 - 2025年03月

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

    栗田 和宏

    　 詳細を見る

    配分額：4810000円 （ 直接経費：3700000円 、 間接経費：1110000円 ）

    今年度は列挙アルゴリズムに関する3編の論文を執筆し，うち1編がデータベース分野のトップ会議であるPODS 2022に採択された．また，列挙アルゴリズムの新たな応用として，ある離散構造の重み和が重い順に上位k個を効率良く計算するアルゴリズムが存在すれば，そのアルゴリズムを用いて多様な組合せ構造を発見する効率良い近似アルゴリズムを開発した．この結果も論文化して現在国際会議に投稿中である．
    列挙アルゴリズム，特に最適化制約を加えた列挙問題に対する近似的な列挙アルゴリズムについては，入力制約問題という特殊な列挙問題が解ける問題に関して，効率良い近似列挙アルゴリズムを与えた．この結果は現在アルゴリズム分野の学術雑誌であるdiscrete applied mathematicsに投稿中である．さらに，この論文で開発した技法を適用できる新たな問題も発見した．具体的には極小な連結辺支配集合が近似的に列挙できることを明らかにした．列挙において頂点に関する連結性を扱うことはしばしば困難になるため，本研究では辺に関する連結性を持つ問題に関して列挙アルゴリズムが構成できるかどうかを研究した．この結果は現在プレプリントとして公開している．
    また，近似的な列挙アルゴリズムは列挙の困難性と最適化の困難性を同時に持つため，近似的な列挙アルゴリズムの研究のためには最適化制約を除いた場合の列挙の研究を深めることも重要である．そこで，本年度は極小なシュタイナー木という辺の連結性に関するグラフの構造に対し，効率良い列挙アルゴリズムの研究を行った．この構造の列挙は2000年台中盤にデータベース分野でも行われており，グラフアルゴリズム分野以外でも興味が持たれている問題である．今年度はこの問題に対して線型遅延の効率良い列挙アルゴリズムを与え，PODS 2022に採択された．

    researchmap

  • 順序制約付き極大部分集合列挙の基盤技術開発

    2021年 - 2023年

    科学技術振興機構  戦略的な研究開発の推進 戦略的創造研究推進事業 ACT-X 

    栗田 和宏

    　 詳細を見る

    担当区分：研究代表者 

    本研究では列挙アルゴリズムの理論と実用のギャップの要因である出力数による計算コストの増加の解決を目指します。列挙では少なくとも出力数に依存した時間が必要です。出力数は膨大なため、効率良い列挙でも膨大な計算コストが必要です。そこで、本研究では出力数を調整可能にするため、順序制約つき列挙に着目します。これにより出力の網羅性と計算コストのトレードオフを実現し、利便性の高い列挙のための基盤技術開発を行います。

    researchmap

  • 疎なグラフに対する効率良い部分構造列挙アルゴリズムの研究

    研究課題/領域番号：19J10761  2019年04月 - 2021年03月

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

    栗田 和宏

    　 詳細を見る

    配分額：1700000円 （ 直接経費：1700000円 ）

    本年度は極大性，極小性を満たす部分グラフ列挙アルゴリズムの開発に加え，サイズ-k列挙アルゴリズムの構築を行なった．その成果として，以下の結果が得られた.
    （1) サイズ-k列挙アルゴリズムは，理論的に扱うことは困難であると考え，ヒューリスティックアルゴリズムの開発を予定していた．しかし，これまでの研究から，サイズ制約付きの列挙問題に対し，妥当な問題の定式化とそれに対する効率良い列挙アルゴリズムの開発に成功した．サイズ制約付き列挙問題を理論的に扱うことが困難な理由として，最適化問題の困難性がある．列挙問題が全ての解を見つける問題であることから，明らかに最適化問題より列挙問題の方が困難であるため，最適化問題の困難性から，サイズ制約付き列挙問題が困難である．この困難性を避けるため，本研究では最適化アルゴリズムのように，列挙問題に近似という概念を導入し，サイズ制約付き列挙問題に対し，近似制約付きの列挙問題を定義した．さらに本研究では近似的なサイズ制約付きの極小部分集合列挙問題に対し，元の列挙問題が容易であるならば，解1つあたり多項式時間で動作する近似列挙アルゴリズムを提案した．
    （2）極小シュタイナー木や内周制約付き極大部分グラフといった疎な部分グラフを列挙する効率良い列挙アルゴリズムの開発を行った．前年度は疎なグラフから部分グラフを効率良くに発見するアルゴリズムを与えたが，本年度はグラフ中から疎な部分グラフを列挙するアルゴリズムについて研究を行い，疎なグラフの中でも代表的な疎なグラフである木構造と，局所的に木構造を持つ内周制約付き極大部分グラフ列挙について研究を行なった．これらの問題に対し，極小シュタイナー木については解1つあたり線形時間，極大内周制約付き部分グラフ列挙については1つあたり多項式時間といった効率良い列挙アルゴリズムが得られた．

    researchmap

▼全件表示

 

担当授業科目

  • 工学安全教育 （2025年度） 第３学期  - 金5～6

  • 工学安全教育 （2025年度） 第３学期  - 金5～6

  • 情報工学実験B (メディア処理) （2025年度） 第３学期  - 火3～7,金3～7

  • 情報工学実験C (ソフトウェア) （2025年度） 第４学期  - 火3～7,金3～7

  • 数理論理学 （2025年度） 第３学期  - 水3～4

  • 数理論理学 （2025年度） 第３学期  - 水3～4

▼全件表示