Maximum agreement subtree problem とは 投稿日: 2018年7月1日 投稿者: csword 最大の合意サブツリー問題は、グラフ理論とコンピュータ科学におけるいくつかの密接に関連する問題のいずれかである。これらの問題のすべてにおいて、 n {\displaystyle n} の葉をそれぞれ含む木の集合 T 1 , … , T m {\displaystyle T_{1},\ldots ,T_{m}} が与えられる。これらの木の葉には、 | L | = n {\displaystyle |L|=n} でいくつかのセット L {\displaystyle L} のラベルが与えられ、同じツリー内に同じラベルを共有する葉のペアはなく、同じツリー内で各リーフのラベルが区別されます。この問題では、 T 1 ∣ S , … , T m ∣ S {\displaystyle T_{1}\mid S,\ldots ,T_{m}\mid S} の L ′ {\displaystyle L’} の葉を含む最小スパン・サブツリーがラベルを保存しながら「同じ」であるように、最大のサブセット L ′ ⊂ L {\displaystyle L’\subset L} を見つけることを望む。原文: Maximum agreement subtree problem (Wikipedia)