文字サイズ
検索

学部・大学院

ホーム > 学部・大学院 > 教員紹介 > 情報・知能工学系 > 和佐 州洋(わさ くにひろ)

和佐 州洋(わさ くにひろ)

所属 情報・知能工学系
職名 助教
専門分野 計算機科学
学位 博士(情報科学)(北海道大学)
所属学会 情報処理学会,人工知能学会,電子情報通信学会
E-mail wasa@cs
※アドレスの末尾に「.tut.ac.jp」を補完してください
研究者情報(researchmap) 研究者情報

テーマ1:部分グラフ列挙問題

概要

見知らぬ街に来て「駅へはどうやっていくのだろう」と思ったとき,あなたはまず,地図を見て経路を探します.大抵の場合は,1つの経路が見つかれば十分です.しかし,1週間滞在することになり,その街のいろいろな風景を見たいあなたは様々な道を通ってその駅に行ってみたくなります.列挙問題は,後者を抽象的に表現した問題と解釈できます.つまり,ある与えられた入力に対して,実行可能な解を全て(あるいは指示された個数)を出力する,という問題です.これは経路だけでなく,高い頻度で購入される商品の組み合わせや,機械学習に利用する特徴量抽出,有用な化合物の候補,など多岐にわたります.列挙問題は実用上においてだけでなく,理論においても非常に興味深い問題です.本研究では,特に実際にアルゴリズムを構成することを目標として,特にグラフ構造に着目した列挙問題を考察します.

主な業績

Alessio Conte, Mamadou M. Kanté, Yota Otachi, Takeaki Uno, and Kunihiro Wasa, "Efficient Enumeration of Maximal k-Degenerate Induced Subgraphs of a Chordal Graph," Theoretical Computer Science, August 10, 2018, in press. doi: 10.1016/j.tcs.2018.08.009;
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, September 01, 2018. doi: 10.1587/transfun.E101.A.1383;
Kunihiro Wasa, Yusaku Kaneta, Takeaki Uno, and Hiroki Arimura, "Constant Time Enumeration of Subtrees with Exactly k Nodes in a Tree", IEICE TRANSACTIONS on Information and Systems, Vol.E97-D, No.3, pp.421-430, March 01, 2014. doi: 10.1587/transinf.E97.D.421;

キーワード

列挙問題,グラフ理論

ページトップへ