Поддерево максимального соответствия: различия между версиями

Финден и Гордон [8] предложили эвристический алгоритм для решения задачи MAST на бинарных деревьях с временем исполнения <math>O(n^5) \;</math>, не гарантирующий оптимального решения. Кубицка, Кубицкий и Макморрис [13] предложили алгоритм с временем <math>O(n^{(0,5 + \epsilon) log \; n)}</math> для той же задачи. Первый алгоритм решения этой задачи за полиномиальное время разработали Стил и Уорноу [15]; время его исполнения составляло <math>O(n^2) \;</math>. Стил и Уорноу также рассматривали случаи небинарных и некорневых деревьев. Этот алгоритм требует <math>O(n^2) \;</math> времени для корневых и некорневых деревьев с фиксированной степенью и <math>O(n^{4,5 \; log \; n} )</math> для корневых и некорневых деревьев произвольной степени. Кроме того, они предложили линейную редукцию от корневого дерева к некорневому. Фарак и Торуп предложили алгоритм с временем исполнения <math>O(nc^{\sqrt{log \; n}})</math> для решения задачи MAST на бинарных деревьях, где <math>c \;</math> – константа величиной больше 1. Для деревьев с произвольной степенью этот алгоритм требует <math>O(n^2 c^{\sqrt{log \; n}}) \;</math> времени для некорневого случая [6] и <math>O(n^{1,5 \; log \; n})</math> – для корневого [7]. Фарак, Пжытычка и Торуп получили алгоритм с временем исполнения <math>O(n \; log^3 n) \;</math> для решения задачи MAST на бинарных деревьях. Као [12] удалось получить алгоритм для этой же задачи с временем исполнения <math>O(n \; log^2 \; n) \;</math>. Для деревьев степени n он выполняется за время <math>O(min \{ n d^2 \; log \; d \; log \; n, n d^{3/2} \; log^3 n \} )</math>.