Multi-Rooted Greedy Approximation of Directed Steiner Trees with Applications
Multi-Rooted Greedy Approximation of Directed Steiner Trees with Applications
复制标题
有向 Steiner 树的多根贪婪逼近及其应用
DOI：
10.1007/s00453-015-9973-1
复制
发表时间：
2015
期刊：
影响因子：
1.1
通讯作者：
Toshihiro Fujito
中科院分区：
文献类型：
--
作者：
Tomoya Hibi;Toshihiro Fujito
我们提出了一个贪婪算法的有向斯坦纳树问题（DST），在任何树植根于任何（未覆盖）终端可以是贪婪的选择的候选人。结果表明，对于任意常数，该算法在多项式时间内运行，输出的有向Steiner树的代价不大于任意限制Steiner树的代价的倍，且该有向Steiner树是这样的Steiner树，其中每一个终端都是最远离根或另一个终端的。从这个结果我们得到：（1）一类图，包括准二部图，其Steiner顶点诱导的路的长度被某个常数所限制，其DST可以在因子之内近似;（2）有向图上的树覆盖问题也可以在因子之内近似.
We present a greedy algorithm for the directed Steiner tree problem (DST), where any tree rooted at any (uncovered) terminal can be a candidate for greedy choice. It will be shown that the algorithm, running in polynomial time for any constant, outputs a directed Steiner tree of cost no larger thantimes the cost of any-restricted Steiner tree, which is such a Steiner tree in which every terminal is at mostarcs away from the root or another terminal. We derive from this result that (1) DST for a class of graphs, including quasi-bipartite graphs, in which the length of paths induced by Steiner vertices is bounded by some constant can be approximated within a factor of, and (2) the tree cover problem on directed graphs can also be approximated within a factor of.