Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications

作者：Hibi Tomoya; Fujito Toshihiro^*

来源：Algorithmica, 2016, 74(2): 778-786.

DOI：10.1007/s00453-015-9973-1

• Approximation algorithms
• Steiner tree problem
• Directed graphs
• Greedy algorithm
• Tree cover problem

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 than times the cost of any -restricted Steiner tree, which is such a Steiner tree in which every terminal is at most arcs 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 O(log n), and (2) the tree cover problem on directed graphs can also be approximated within a factor of O(log n).

• 出版日期2016-2