Maximum agreement subtree problem とは

最大の合意サブツリー問題は、グラフ理論とコンピュータ科学におけるいくつかの密接に関連する問題のいずれかである。これらの問題のすべてにおいて、 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} を見つけることを望む。