4501
правка
Поддерево максимального соответствия (для трех или более деревьев): различия между версиями
Перейти к навигации
Перейти к поиску
Поддерево максимального соответствия (для трех или более деревьев) (посмотреть исходный код)
Версия от 14:02, 25 сентября 2015
, 25 сентября 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
Примечание 1. Если mast( | Примечание 1. Если <math>mast(\overrightarrow{v}) > 0 \;</math>, то <math>\overrightarrow{v} = (lca^{T^1} (a, b), ..., lca^{T^k} (a, b)) \;</math> для некоторых меток листьев a, b, где <math>lca^{T^i} (a, b) \;</math> – самый низкий общий предок листьев с метками a и b в дереве V. | ||
Кортеж v, такой, что v = ( | |||
Кортеж <math>\overrightarrow{v} \;</math>, такой, что <math>\overrightarrow{v} = (lca^{T^1} (a, b), ..., lca^{T^k} (a, b)) \;</math> для некоторых <math>a, b \in A \;</math>, называется lca-кортежем. Согласно примечанию 1, достаточно вычислить значения mast только для lca-кортежей. Как и при использовании наивного подхода, <math>mast(\overrightarrow{v}) \;</math> вычисляется из значений mast других lca-кортежей, доминируемых <math>\overrightarrow{v} \;</math>. Еще одно важное наблюдение заключается в том, что для вычисления <math>mast(\overrightarrow{v}) \;</math> необходимы только некоторые lca-кортежи, доминируемые <math>\overrightarrow{v} \;</math>. Чтобы реализовать его, Фарах и коллеги определяют так называемое отношение истинного доминирования и показывают, что значение mast для любого lca-кортежа <math>\overrightarrow{v} \;</math> может быть вычислено из значений mast lca-кортежей, истинно доминируемых <math>\overrightarrow{v} \;</math>, и что отношение истинного доминирования имеет размер <math>O(n^3) \;</math>. | |||