Kazuhiro Kurita

Affiliation: Information Knowledge Network Laboratory, Division of Computer Science and Information Technology, Graduate School of Information Science and Technology, Hokkaido University.

2019 - Present: Japan Society for the Promotion of Science Research Fellowships for Young Scientists (DC2).

e-mail: k-kurita(at)ist.hokudai.ac.jp

Publications

Journal Papers

  1. Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, and Hiroki Arimura, "Efficient Enumeration of Induced Matchings in a Graph without Cycles with Length Four," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E101.A, No.9, pp.1383-1391, 2018.


Inter national conference (referred)

  1. Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, and Hiroki Arimura, "An Efficient Algorithm for Enumerating Chordal Bipartite Induced Subgraphs in Sparse Graphs," Proceedings of 30th International Workshop on Combinatorial Algorithm (IWOCA 2019), Lecture Notes in Computer Science , vol. 11638, pp. 339-351, 2019.
  2. Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, and Takeaki Uno, "Efficient Enumeration of Dominating Sets for Sparse Graphs," Proceedings of 29th International Symposium on Algorithms and Computation (ISAAC 2018), Leibniz International Proceedings in Informatics , vol. 123, pp.8:1 - 8:13, 2018, Acceptance rate: 71/195.
  3. Kazuhiro Kurita, Kunihiro Wasa, Alessio Conte, Takeaki Uno, and Hiroki Arimura, "Efficient Enumeration of Subgraphs and Induced Subgraphs with Bounded Girth," Proceedings of 29th International Workshop on Combinatorial Algorithm (IWOCA 2018), Lecture Notes in Computer Science, vol. 10979 , pp. 201-213, 2018, Acceptance rate: 31/69. There is a correction in the proceedings paper. See the corrected slide
  4. Alessio Conte, Kazuhiro Kurita, Kunihiro Wasa, and Takeaki Uno, "Listing acyclic subgraphs and subgraphs of bounded girth in directed graphs," Proceedings of 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2017), Lecture Notes in Computer Science , vol.10628, pp. 169-181, 2017, Acceptance rate: 59/145.


International conferences (not referred)

  1. Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, and Hiroki Arimura "Subgraph Enumeration: Efficient Algorithms and Empirical Studies," 2nd International Workshop on Enumeration Problems & Applications, Pisa University, Pisa, November 6, 2018
  2. Kazuhiro Kurita, Alessio Conte, Kunihiro Wasa, Takeaki Uno, and Hiroki Arimura "Efficient Enumeration Algorithms for Connected Induced Subgraphs with Large Girth," 20th Korea-Japan Joint Workshop on Algorithms and Computation(WAAC 2017), Hanyang University, Seoul, August 26, 2017, PDF
  3. Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, and Hiroki Arimura, "Efficient Enumeration of Induced Matchings in Graphs without Short Cycles," 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games 2016 (JCDCG3 2016), Tokyo Univ. of Science, Tokyo, September 4, 2016


Preprint

1. Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, and Takeaki Uno "Constant Amortized Time Enumeration of Independent Sets for Graphs with Bounded Clique Number." 2019. [pdf]

Domestic conferences (not referred)

  1. 栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀, "最大クリークサイズが定数であるグラフに対する独立点集合のならし定数時間列挙," 電子情報通信学会 コンピューテーション研究会, COMP, vol. IEICE-119, 249, pp. 11-18 , 2019
  2. 栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀, "最大クリークサイズが定数であるグラフに対する独立点集合の効率良い線形領域列挙アルゴリズム," 列挙合宿, 伊香保温泉, 群馬, 2019年04月23日
  3. 堀山貴史,栗田和宏,岡本吉央,内澤啓,上原隆平, "Mind the Mind with Synchronous Clocks," 組合せゲーム・パズル(CGP) プロジェクト 第14回研究集会, 電気通信大学, 東京, 2019年3月11日
  4. 栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀, "固定クリーク数グラフに対する誘導木のならし定数時間列挙," 2018年度 冬のLAシンポジウム, 京都大学数理解析研究所, 京都, 2019年2月5日
  5. Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, and Hiroki Arimura , "An Efficient Algorithm for Enumerating Chordal Bipartite Induced Subgraphs in Graphs," 研究報告アルゴリズム(AL), vol. 2019-AL-171, 9, pp. 1-7, 2019.
  6. 伝住周平, 堀山貴史, 栗田和宏, 中畑 裕, 鈴木浩史, 和佐州洋, 山崎一明, "非同型な2端子直並列グラフの列挙とランダムサンプリング," 電子情報通信学会 コンピューテーション研究会, COMP, vol. IEICE-118, 216, pp. 55-62, 2018.
  7. 栗田 和宏, Alessio Conte, 和佐 州洋, 宇野毅明, 有村博紀, "グラフに含まれる大きな内周を持つ部分グラフの効率良い列挙," 情報処理学会第80回全国大会, 第80回全国大会講演論文集, vol. 2018, 1, pp. 347-348, 2018
  8. 栗田 和宏, 和佐 州洋, 有村 博紀, 宇野 毅明, "k-縮退グラフに含まれる支配集合の列挙アルゴリズム," Foundations and Applications of Algorithms and Computation アルゴリズムと計算理論の基礎と応用, vol. 2018, 2088, 2018.(2017年度 冬のLAシンポジウムで口頭発表済み)
  9. 坂上 陽規, 栗田 和宏, 瀧川 一学, 有村 博紀, ”決定化されたグラフパターントライの学習アルゴリズム,” 人工知能学会 第105回人工知能基本問題研究会, SIG-FPAI, vol. B5, 08, pp. 63-68, 2018
  10. 栗田 和宏, 和佐 州洋, 有村 博紀, 宇野 毅明 "定数縮退グラフに含まれる支配集合の最適な列挙," 列挙合宿, 伊香保温泉, 群馬, 2018年01月18日
  11. Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura "An Efficient Enumeration Algorithm for Dominating Sets in K-Degenerate graphs," 電子情報通信学会 コンピューテーション研究会, COMP, vol. IEICE-117, 370, pp. 111-117, 2017.
    • 論文の訂正について 2017年12月22日開催の電子情報通信学会 コンピュテーション研究会で発表の"An Efficient Enumeration Algorithm for Dominating Sets in K-Degenerate graphs"の結果がO(k) time per solutionだったが間違いだった.これは現在修正されて最終的にはO(k^2) time per solutionである.最終的な結果である定数縮退数グラフに対して,定数ならし時間であるという主結果に変更はない.修正版PDF
  12. 栗田 和宏, Alessio Conte, 和佐 州洋, 宇野 毅明, 有村 博紀 "グラフに含まれる内周k以上の連結誘導部分グラフの効率良い列挙," 2017年度 夏のLAシンポジウム, 天童温泉, 山形, 2017年7月19日
  13. 栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀, "グラフに含まれる大きな内周の連結な誘導部分グラフの列挙," 列挙合宿, 伊香保温泉, 群馬, 2017年07月5日
  14. 栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀, "短いサイクルのないグラフに対する誘導マッチングの効率の良い列挙," 列挙合宿, 伊香保温泉, 群馬, 2016年10月12日
  15. 栗田 和宏, 和佐 州洋, 喜田 拓也, 有村 博紀, "グラフに含まれる誘導マッチングの列挙," 研究報告アルゴリズム(AL), vol. 2016-AL-157, 10, pp. 1-6, 2016.
  16. 笹川 裕人, 山本 雅大, 栗田 和宏, 有村 博紀 "大規模トラジェクトリ照合のためのビット並列計算を用いた省メモリアルゴリズム," 第7回Webとデータベースに関するフォーラム (WebDB Forum 2014), 芝浦工業大学・豊瀬キャンパス, 東京, 2014年12月19日. (学生奨励賞受賞)
  17. 栗田 和宏, 和佐 州洋, 有村 博紀, "プログラミングコンテストにみる最適化," 列挙合宿 伊香保温泉, 群馬, 2014年9月
  18. 笹川 裕人, 山本 雅大, 栗田 和宏, 有村 博紀, "大規模トラジェクトリ照合のためのビット並列計算を用いた省メモリアルゴリズム," 第7回Webとデータベースに関するフォーラム(WebDB Fourum 2014

Award

  1. 栗田 和宏 学生奨励賞. , 第7回Webとデータベースに関するフォーラム (WebDB Forum 2014) ,2014年11月20日. (大規模トラジェクトリのためのビット並列計算を用いた省メモリアルゴリズム,笹川 裕人,山本 雅大,栗田 和宏,,有村 博紀, 第7回Webとデータベースに関するフォーラム (WebDB Forum 2014, 芝浦工業大学・豊洲キャンパス,2014年11月

Other

  1. Alessio Conte, Kazuhiro Kurita, Yasuaki Kobayashi, Roberto Grossi, Giulia Punzi, "モジュラー分解を用いた極大クリークの効率よい列挙と数え上げに向けて," 湊基盤(S)2019年度秋のワークショップ,丸駒温泉, 北海道, 2019年11月5日
  2. 栗田和宏, 和佐州洋, 有村博紀, 宇野毅明, "頂点数定数の禁止部分グラフを持つグラフに 対する独立点集合のならし定数時間列挙," 湊基盤(S)2019年度初夏のワークショップ, 北海道大学, 北海道, 2019年06月21日
  3. 栗田和宏, 和佐州洋, 有村博紀, 宇野毅明, "定数クリーク数グラフに対する独立点集合のならし定数時間列挙," 湊基盤(S)2018年度 秋のワークショップ, 第一滝本館, 北海道, 2018年11月25日
  4. Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno, "Efficient Enumeration Algorithms for Dominating sets in Sparse Graphs," The 2nd GI-CoRE GSQ, GSB & IGM Joint Symposium, Hokkaido University, Hokkaido, August 8, 2018
  5. 栗田和宏, 和佐州洋, 有村博紀, 宇野毅明, "二部グラフに含まれる弦二部誘導部分グラフのならし線形時間列挙に向けて," 湊基盤(S)2018年度 初夏のワークショップ 北海道大学, 北海道, 2018年07月07日
  6. 栗田 和宏, Alessio Conte, 和佐 州洋, 宇野 毅明, 有村 博紀, "グラフ中の内周k以上の部分グラフと誘導部分グラフの効率良い列挙," 情報系WINTER FESTA Episode 3, 一橋講堂, 東京, 2017年12月25日
  7. 栗田和宏, 和佐 州洋, 宇野 毅明, 有村 博紀 "k-縮退グラフに含まれる支配集合の効率良い列挙に向けて," 湊基盤(S)2017年度 秋のワークショップ, ホテル五味, 北海道厚岸, 2017年11月13日
  8. 栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀 "グラフに含まれる大きな内周を持つ連結誘導部分グラフの効率良い列挙," 湊基盤 (S)2017年度 初夏のワークショップ, 北海道大学, 北海道, 2017年6月24日
  9. 栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀 "C4-freeグラフに対する効率の良い誘導マッチングの列挙," 湊基盤 (S) 2016年度 秋のワークショップ, ガトーキングダム, 北海道, 2016年11月20日
  10. 栗田 和宏, 和佐 州洋, 宇野 毅明, 有村 博紀 "小さい閉路のないグラフに対する効率の良い誘導マッチングの列挙," 湊基盤 (S) 2016年度 初夏のワークショップ, 2-3, 北海道大学, 北海道, 2016年6月17日
  11. 栗田 和宏, 和佐 州洋, 喜田 拓也,有村 博紀, "グラフに含まれる誘導マッチングの列挙," STRセミナー 2016, 北海道, 北海道大学, 2016年3月22日
  12. 栗田 和宏, "速度制限付きグラフ上の最短時間路問題に対する擬似多項式時間アルゴリズム," STRセミナー 2015, 別府国際コンベンションセンター, 大分, 2015年3月

Program Code

  1. Enumeration of bounded girth subgraph
  2. Enumeration of induced matching

Biography

平成20年 (2008年) 3月31日 栃木県西那須野中学校 卒業

平成20年 (2008年) 4月1日 栃木県大田原高校 入学

平成23年 (2011年) 3月31日 栃木県大田原高校卒業

平成23年 (2011年) 4月1日 北海道大学総合理系 入学

平成27年 (2015年) 3月31日 北海道大学工学部 情報エレクトロニクス学科 コンピュータサイエンスコース卒業

平成27年 (2015年) 4月1日 北海道大学 大学院情報科学研究科 情報理工学専攻 修士課程 入学

平成29年 (2017年) 3月31日 北海道大学 大学院情報科学研究科 情報理工学専攻 修士課程 卒業

平成29年 (2017年) 4月1日 北海道大学 大学院情報科学研究科 情報理工学専攻 博士課程 入学

平成30年 (2018年) 8月 インターンシップ(日立製作所 中央研究所)

Teaching experience

平成30年(2018年) 4月1日 ~ 現在 北海学園大学非常勤 講師(工学部)

平成29年(2017年) 9月1日 - 平成30年3月31日 北海学園大学非常勤 講師(工学部)

北海道大学 工学部 情報エレクトロニクス学科 情報理工学コース 情報理工学演習III ティーチングフェロー(TF),04/2017 - 08/2017 講義資料

北海道大学 工学部 情報エレクトロニクス学科 情報理工学コース 情報理工学実験I ティーチングアシスタント(TA), 05/2017

北海道大学 工学部 情報エレクトロニクス学科 情報理工学コース 情報理工学演習III ティーチングアシスタント(TA), 04/2016 - 07/2016

北海道大学 工学部 情報エレクトロニクス学科 情報理工学コース 情報理工学実験I ティーチングアシスタント(TA), 05/2016

License

平成29年(2017年) 5月16日 普通自動車免

Other Activity

  1. Sub reviewer: STACS 2019, IWOCA 2019
  2. ACM ICPC Domestic Preliminary Contest 2015, 24th/316, Award, team name: tsurasa_diary, June, 201
  3. ACM ICPC Asia Tsukuba Regional Contest 2015, 25th/42, team name: tsurasa_diary, November, 201
  4. The 2015 ACM-ICPC Asia Taipei Regional Contest 18th/72, team name: tsurasa_diary, December, 201TopCoder: kazu0423