论文标题
在类似树的指标中的啤酒花限制的坦者树上
On Hop-Constrained Steiner Trees in Tree-Like Metrics
论文作者
论文摘要
我们考虑在啤酒花约束下计算最低成本的施泰纳树的问题，这需要树的深度最多为$ k $。我们的主要结果是由具有有限树宽的图形引起的指标的精确算法，该算法在时间$ n^{o（k）} $中运行。对于路径的特殊情况，我们提供了一种简单的算法，即使$ k $是输入的一部分，也可以在多项式时间内解决问题。主要结果可用于在准多项式时间中获得一个近乎最佳的解决方案，它最多可以通过一个跳跃来违反$ k $ -HOP的约束，从而通过有限的高速公路尺寸和有限的加倍尺寸引起的更通用的指标。对于非金属图，我们排除$ O（\ log n）$ - 近似值，即使在任何添加剂常数放松啤酒花约束时，也会假设p $ \ neq $ np。
We consider the problem of computing a Steiner tree of minimum cost under a hop constraint which requires the depth of the tree to be at most $k$. Our main result is an exact algorithm for metrics induced by graphs with bounded treewidth that runs in time $n^{O(k)}$. For the special case of a path, we give a simple algorithm that solves the problem in polynomial time, even if $k$ is part of the input. The main result can be used to obtain, in quasi-polynomial time, a near-optimal solution that violates the $k$-hop constraint by at most one hop for more general metrics induced by graphs of bounded highway dimension and bounded doubling dimension. For non-metric graphs, we rule out an $o(\log n)$-approximation, assuming P$\neq$NP even when relaxing the hop constraint by any additive constant.
