Вестник Московского Университета. Математика, Механика - Содержание


УДК 517.958:57

Алгоритм Мелзака для филогенетических пространств / Иванов А.О., Тужилин А.А., Цислик Д. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2002. N.3 C. 22-28.

В статье приведен алгоритм построения минимального дерева $\Gamma $ заданной топологии $G$, затягивающего конечное подмножество $N=\{\beta _1,\ldots,\beta _n\}$ филогенетического пространства. Скорость алгоритма имеет порядок $2^n\,\vert\beta _1\vert\cdots\vert\beta _n\vert$, где $\vert\beta \vert$`-- длина слова $\beta $. Как следствие получен алгоритм построения точки Симпсона-Торричелли для множества $N$, в частности алгоритм построения минимального дерева Штейнера для трехточечного множества.

Библиогр. 9.

К оглавлению номера  Go!