部分二部グラフの列挙と応用

概要

あるグラフ構造が与えられた時、そのグラフから制約条件を満たすような部分グラフ構造を列挙することは、現実でも必要に迫られることが多々ある重要な手続きである。本発表では、あるグラフGが与えられた時、その部分グラフでかつ二部グラフであるものをZDDを用いて効率的に列挙し、またその応用について述べる。ZDDとは二部決定グラフBDDを改良したものあり、冗長な節点を削除する規則の違いから特に疎な組み合わせの集合について顕著な効果がある。

産業界への展開例・適用分野

本発表で取り扱う二部グラフは、研修医を病院に配属する問題や、子どもを保育所に割当てる問題など、マッチングと呼ばれる問題を定式化する際に現れる構造である。ZDDを用いた二部グラフの列挙により、最適解を1つ求めるだけではなく、社会で要望される様々な条件を満たす解を複数求め、比較することが可能となる。

研究者

氏名	専攻	研究室	役職/学年
吉村 知行	通信情報システム専攻	湊研究室	修士1回生
川原 純	通信情報システム専攻	湊研究室	准教授
湊 真一	通信情報システム専攻	湊研究室	教授

---