２０２３年９月６日（水）に崇城大学で電子情報通信学会九州支部学生会講演会がオンラインで開催され、本学情報工学部知能情報工学科４年生の今村 遥弥さんによる講演「順序付き区間グラフに対する部分グラフ同型性判定問題に対する考察」が学生会講演奨励賞を受賞しました。
本研究で扱っている部分グラフ同型性判定問題は計算量理論上、困難な問題であり、入力のグラフを区間グラフに制限しても計算困難であることが知られています。それに対し、区間グラフは時系列データから自然に現れるグラフで、時系列情報から頂点の順序などの情報を自然に与えることができます。本研究はそうした自然な頂点順序を持つ区間グラフ上での部分グラフ同型性判定問題に対する効率的なアルゴリズムを提案しており、このアルゴリズムは時系列データ解析などへの応用が期待できます。

受賞した今村 遥弥さん