An FPT algorithm in polynomial space for the Directed Steiner Tree problem with Limited number of Diffusing nodes

作者：Watel Dimitri^*; Weisser Marc Antoine; Bentz Cedric; Barth Dominique

来源：Information Processing Letters, 2015, 115(2): 275-279.

DOI：10.1016/j.ipl.2014.09.027

• Directed Steiner Tree
• Parameterized complexity
• Dynamic programming
• Algorithms
• Combinatorial problems

Given a directed graph with n nodes, a root r, a set X of k nodes called terminals and non-negative weights omega over the arcs, the Directed Steiner Tree problem (DST) asks for a directed tree T* of minimum cost omega(T*) rooted at r and spanning X.
If this problem has several applications in multicast routing in packet switching networks, the modeling is no longer adapted in networks based upon the circuit switching principle, in which some nodes, called non-diffusing nodes, are not able to duplicate packets. We study a generalization of DST, called Directed Steiner Tree with Limited number of Diffusing nodes (DSTLD), able to model the multicast routing in a network containing at most d diffusing nodes.
We provide an FPT exact algorithm running in time O (t(d) . d(k) . n . (d + k)) and in polynomial space for DSTLD, where t(d) is the number of unordered rooted trees with d unlabelled nodes. Thereby, we also provide the first exact algorithm running in polynomial space and in FPT time with respect to k which returns an optimal solution for DST instead of the optimal cost only.

• 出版日期2015-2