学術情報メディアセンターセミナー「グラフアルゴリズムの進展」

プログラム

16時30分～17時30分

講演者

大舘 陽太（熊本大学先端科学研究部 准教授）

講演題目

グラフ同型性判定問題の紹介

講演概要

グラフ同型性判定問題とは、二つのグラフが与えられた時にその二つが「同じ」であるかどうか判定する問題です。この問題はグラフに関する問題で最も自然なものであるにも関わらず、高速なアルゴリズムも困難性も知られていません。この問題に対する研究の歴史、既知の結果、最近の進展などについて紹介します。

17時30分～18時30分

講演者

小林 靖明（京都大学情報学研究科 助教）

講演題目

木幅と動的計画法

講演概要

木幅はグラフがどれだけ「木のような構造」を持つかを表す指標であり、RobertsonとSeymourの有名なグラフマイナー定理の中で重要な役割を果たすだけでなく、アルゴリズムを設計する上でも重要な概念のひとつとして認識されています。本講演では、グラフの木幅や木分解といった概念を説明し、それらを用いた動的計画法について解説します。さらに、それらの動的計画法を高速化するためのテクニックについても概観します。