Алгоритм Мелзака в филогенетических пространствахстатья
Статья опубликована в журнале из списка RSCI Web of Science
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 16 февраля 2016 г.
Аннотация:В статье приведен алгоритм построения минимального дерева $\Gamma$ заданной топологии $G$, затягивающего конечное подмножество $N=\{\beta _1,\ldots,\beta _n\}$ филогенетического пространства. Скорость алгоритма имеет порядок $2^n\,\vert\beta _1\vert\cdots\vert\beta _n\vert$, где $\vert\beta \vert$ --- длина слова $\beta$. Как следствие получен алгоритм построения точки Симпсона-Торричелли для множества $N$, в частности алгоритм построения минимального дерева Штейнера для трехточечного множества.