| 概要 | マッチング問題と有向森問題は効率的に扱える組合せ最適化問題の
代表例であり，これらに対する組合せ的アルゴリズムや線形計画表現の
完全双対整数性は組合せ最適化における基本的な結果である．
マッチング森問題はこの二つの問題の共通の一般化であり，
多項式時間可解性や完全双対整数性を継承している．
一方，デルタマトロイドはある交換公理を満たす集合族と定義され，
デルタマトロイド構造を持つ組合せ最適化問題は効率的に扱えると
認識されている．例えばマッチングの端点集合の族はデルタマトロイドを
成すことが知られている．
本講演では，マッチング森の新たな一面として，マッチング森の端点集合の族が
デルタマトロイドを成すこと，およびその拡張として重みつきマッチング森が
付値デルタマトロイドを導出することを紹介する．さらに，
デルタマトロイド構造に注目したマッチング森アルゴリズムの解析を行う． |