О полиномиальной разрешимости ультраметрических версий некоторых NP-трудных задач

Статья посвящена анализу важных частных случаев задачи коммивояжера и задачи Штейнера. Обе эти задачи являются NP-трудными даже в метрическом случае, т. е. для графов, у которых функция стоимости ребер удовлетворяет неравенству треугольника. Более строгим ограничением является усиленное неравенство треугольника: $ \forall x,y,z \in X \quad c(x,z) \leq \max\{c(x,y), c(y,z)\} $. Метрические функции, удовлетворяющие такому условию, называются ультраметрическими. В статье на основе анализа графов с ультраметрической функцией стоимости ребер разработан алгоритм, позволяющий построить для такого графа гамильтонов цикл минимальной стоимости за время $O(n^2)$, где $n$ — число вершин графа. Для задачи Штейнера показано, что при ультраметрической функции стоимости ребер минимальное дерево Штейнера содержит только терминальные вершины и поэтому также может быть построено за полиномиальное время как минимальное остовное дерево на подграфе исходного графа.