Деревья Штейнера: различия между версиями

Все вышеперечисленные аппроксимации были созданы на базе семейства k-ограниченных деревьев Штейнера. В результате улучшения некоторых деталей построения константный коэффициент эффективности удалось понизить, однако при этом улучшения также становятся меньше. В 1996 году Ароре [ ] удалось достичь значительного прогресса в решении задач EST и RST. Он доказал существование PTAS для этих двух задач. Таким образом, исследователи-теоретики теперь основное внимание уделяют задаче NST. Берн и Плассман [ ] показали, что эта задача является MaxSNP-полной. Это означает, что существует положительное число r, такое, что вычисление r-аппроксимации для NST является NP-полной задачей. Самый эффективный на данный момент алгоритм построения NST предложили Робин и Зеликовский [12]. Они также дали очень простой анализ хорошо известной эвристики – итеративного 1-дерева Штейнера для псевдодвудольных графов.