09 2018/10 11
300102 03040506
07080910111213
14151617181920
2122 2324252627
28293031010203
Click セミナー

過去のセミナー

開催日2018年4月18日(水曜日)
開催時間16時30分-17時30分
発表者山口 勇太郎 
発表者の紹介大阪大学/ACT-i
タイトル2部グラフのマッチングに関する離散構造 
発表の概要
2部グラフにおけるマッチング問題は,行列に関する組合せ構造の理論的な解析や,結婚問題をはじめとする社会的メカニズムの設計への応用など,古くから様々な文脈で研究されている古典的な問題である.本発表では,2部グラフのマッチングに関する離散構造について,基本的な話題から始め,自身の最近の研究成果を紹介する.
開催場所VBL 301B
接続サイト神田オフィス,京大ラボ
 
開催日2018年4月18日(水曜日)
開催時間17時30分-18時30分
発表者増井 隆治 
発表者の紹介京都大学
タイトル Enumerating Trees by Dynamic Programming 
発表の概要
The enumeration of graphs with a restricted structure is a classical problem in graph theory, with important applications including the enumeration of chemical compounds.

We focus on the enumeration of trees, and propose an algorithm based on dynamic programming that generates all unique trees on $n$ vertices with a given maximum degree at most $¥Delta$.
The assumption on the restricted degree can be omitted by setting
$¥Delta = n-1$.
The recursive relations used for the dynamic programming
are based on an encoding scheme for rooted trees,
which we also use to define a total order among trees.

Our algorithm first counts the number of rooted trees using dynamic programming in $¥mathcal{O}(n^2 ¥Delta^2)$ time and $¥mathcal{O}(n^2 ¥Delta)$ space.
Following, using the information from this counting phase,
the algorithm can generate all trees in a sequential manner following the prescribed order, without generating isomorphic trees, using $¥mathcal{O}(n)$ time per tree and $¥mathcal{O}(n^2 ¥Delta)$ space in total.
We conduct computational experiments and conclude that our implementation of the algorithm runs faster when compared to state-of-the-art enumeration programs for chemical compounds that we use as generators of trees with bounded degree four.
開催場所VBL 301
接続サイト神田オフィス,京大ラボ