Задача о поддереве максимального согласия

Проблема поддерева максимального согласия — это одна из нескольких тесно связанных проблем теории графов и информатики . Во всех этих задачах дан набор деревьев. $T_{1},\ldots ,T_{m}$ каждый из которых содержит $n$ листья. Листьям этих деревьев присвоены метки из некоторого множества. $L$ с $|L|=n$ так что ни одна пара листьев в одном дереве не имеет одной и той же метки, внутри одного дерева маркировка для каждого листа различна. В этой задаче хотелось бы найти наибольшее подмножество $L'\subset L$ такие, что минимальные остовные поддеревья, содержащие листья в $L'$ , из $T_{1}\mid S,\ldots ,T_{m}\mid S$ являются «одинаковыми», сохраняя при этом маркировку.

Составы

Поддерево максимального гомеоморфного согласия ^[1]

Эта версия требует, чтобы поддеревья $T_{1}\mid S,\ldots ,T_{m}\mid S$ гомеоморфны . друг другу

Корневое поддерево максимального гомеоморфного согласия

Эта версия аналогична поддереву максимального гомеоморфного согласия , но мы далее предполагаем, что $T_{1},\ldots ,T_{m}$ имеют корни и что поддеревья $T_{1}\mid S,\ldots ,T_{m}\mid S$ содержать корневой узел. Эта версия задачи о поддереве максимального согласия используется для изучения филогенетических деревьев . ^[1] Из-за своей тесной связи с филогенией эта формулировка часто имеет в виду проблему «поддерева максимального согласия».

Другие варианты

Существуют и другие формулировки, например (корневое) поддерево максимального изоморфного согласия. ^[1] где мы требуем, чтобы поддеревья были изоморфны друг другу.

См. также

Частый майнинг поддеревьев

Ссылки

^ Jump up to: ^а ^б ^с Амир, А.; Кесельман, Д. (1 декабря 1997 г.). «Поддерево максимального согласия в наборе эволюционных деревьев: метрики и эффективные алгоритмы». SIAM Journal по вычислительной технике . 26 (6): 1656–1669. CiteSeerX 10.1.1.133.6891 . дои : 10.1137/S0097539794269461 . ISSN 0097-5397 .

Као, Мин-Ян; Лам, Так-Ва; Сун, Крылатый Род; Тинг, Хинг-Фунг (август 2001 г.). «Еще более быстрый и более унифицированный алгоритм сравнения деревьев посредством несбалансированных двусторонних сопоставлений». Журнал алгоритмов . 40 (2): 212–233. arXiv : cs/0101010 . дои : 10.1006/jagm.2001.1163 .

[:0-1] Jump up to: ^а ^б ^с Амир, А.; Кесельман, Д. (1 декабря 1997 г.). «Поддерево максимального согласия в наборе эволюционных деревьев: метрики и эффективные алгоритмы». SIAM Journal по вычислительной технике . 26 (6): 1656–1669. CiteSeerX 10.1.1.133.6891 . дои : 10.1137/S0097539794269461 . ISSN 0097-5397 .

[1]