平成 24 年度第 5 回 OR横断若手の会(KSMAP)


第 5 回
日  時:2 月 22 日 (金)
出席者: 13 人
場  所:京都大学数理解析研究所111号室

テーマと講師:
(1) 斎藤寿樹 (神戸大学)
「ZDDを用いたグラフ列挙索引化とその応用」

ZDDとは組合せ集合を効率的に保持するデータ構造であり,計算問題や最適化問
題の解の絞り込みや最適解の抽出などに役立つ技術である.本発表では,Knuth
によるZDDを用いたパス列挙アルゴリズムや,それを拡張した様々なグラフ構造
の列挙アルゴリズムが紹介された.また,電力網設計などへの応用研究の成果に
ついても解説がされた.

(2) Jesper Jansson (京都大学)
「Combinatorial Algorithms for Constructing a Phylogenetic Supertree」

系統樹とは,生物学的種やタンパク質,自然言語やスパムメールなどの進化の過
程を記述するためのデータ構造である.本発表では,近年バイオインフォマティッ
クスの分野で注目されているトピックである,与えられた複数の系統樹をできるだ
け情報を損なわないように一つの系統樹にまとめるためのアルゴリズムについて紹
介がされた.特に,根付きトリプレットと呼ばれる系統樹の集合から一つの系統樹
を構築するアルゴリズムやその拡張について解説がされた.


13名の方々に御参加いただきました.御礼申し上げます.
福永 拓郎
最終更新日: 2013年2月25日