グラフ構造とグラフアルゴリズム

頂点と隣接関係を表すグラフは、コンピューターサイエンスのどの分野でも出現する対象である。本講義では、グラフに現れるローカル、あるいはグローバルな構造とグラフアルゴリズムの関係性を解説する予定である。また、木幅などの、グラフを対象とする不変量とグラフアルゴリズムの関係も解説予定である。
　基本的には、グラフの構造解析を理論的に行うことを主眼とするが、グラフベンチワークに対する高速アルゴリズム開発も演習、あるいは課題に入れる予定である。

Graphs appear everywhere in computer science. It turns out that, in order to develop efficient algorithms, one needs to understand graph structures. In this lecture, we highlight graph structures and algorithms. Topics include expander graphs, planar graphs and social networks. Moreover, graph invariants, like tree-width, play an important role to develop graph algorithms. We will introduce some graph invariants that help to develop fast and scalable algorithms.