The 29th International Computing and Combinatorics Conference (COCOON 2023) は、アルゴリズム、計算理論、計算複雑性、および組み合わせ論の分野における研究発表が行われる国際会議である。計算機理論分野の会議としては比較的長い歴史を持ち、アジア圏のみならず欧米圏からも多数の発表者が参加する。
COCOON 2023での研究発表は、実社会上で現れる問題に対して、その問題を効率的に解決可能なアルゴリズムは存在するかどうか、一般的に可能でなければどのような状況であれば可能か、という疑問を理論的な観点から扱ったものが中心である。その一方で、現実の環境を基に実験を行い、アルゴリズムの有用性と効率性を示す応用研究も多く行われている。
今年はアメリカ合衆国ハワイ州のホノルルにて2023年の12月15日から17日までの計3日間開催され、2件の招待講演と60件の口頭発表が行われた。
【題名】
On the Routing Problems in Graphs with Ordered Forbidden Transitions
【研究テーマ】
道路網上の2地点間の経路を見つける問題（経路問題）は、古くから様々な研究がされてきており、一般には幅優先探索やダイクストラ法といった基礎的なアルゴリズムが適用可能である。しかし、実際の道路網には、指定方向外進行禁止（左折禁止等）が指定されている交差点が存在するため、前述のアルゴリズムをそのまま適用することはできない。本論文では、指定方向外進行禁止の制約を加えた道路網において始点から終点までの経路を見つける問題を扱い、問題の計算複雑性を明らかにするため、困難性・容易性の両面から研究を行った。具体的には、立体交差が無く、交差点が全て三叉路であるような非常に限られた道路網に対しても、この問題を高速に解くアルゴリズムが存在しそうにないと理論的に証明した。一方で、木幅と呼ばれるパラメータの小さい道路網に対しては効率的に動作する、動的計画法をベースとしたアルゴリズムを与えた。
【討論内容】
発表時間の都合上説明できなかった研究結果におけるアルゴリズムの手法と、経路に対する制限の加え方（経路が同じ地点を複数回通過することを許すか）による計算複雑性の違いについて説明を行った。
今回は自身にとって初めての国際会議の参加であった。英語を用いた発表に慣れていなかったため、念入りに準備をして本番に臨んだ。その甲斐もあり発表そのものはスムーズに終えることができたが、発表中に聴衆を見て内容を伝える姿勢がまだ足りないと感じた。また、質疑応答では、質問内容は聞き取ることができたが、すぐに良い説明が思いつかず、かなり簡潔な回答になってしまった。今回の国際会議で得た反省点は、英語・日本語を問わず今後研究発表を行う際に生かしたい。
また、別の研究者の発表では自身の研究テーマに近い内容の発表もあり、今後の自身の研究方針について考えるにあたって非常に参考になった。
さらに、この会議が開催されたハワイでの生活も、報告者にとって新鮮なものだった。ホテルや飲食店、公共交通機関においてコミュニケーションが必要な機会があったが、そこで今まで学んだ英語を役立てることができて、英会話に対する自信につながった。
最後に、本国際会議への参加にあたり、貴財団より多大なるご支援をいただきましたこと、心より感謝申し上げます。
