|
 
|
[WWB15] An FPT algorithm in polynomial space for the Directed Steiner Tree problem with Limited number of Diffusing nodes
Revue Internationale avec comité de lecture : Journal Information processing letters, vol. 115(2), pp. 275-279, 2015, (doi:10.1016/j.ipl.2014.09.027)Mots clés: Directed Steiner Tree, Parameterized complexity, Dynamic programming Algorithms, Combinatorial problems
Résumé:
Given a directed graph with n nodes, a root r, a set X of k nodes called terminals and non-negative weights ω over the arcs, the Directed Steiner Tree problem (DST) asks for a directed tree of minimum cost 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 and in polynomial space for DSTLD, where 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.
Equipe:
oc
BibTeX
| @article { | |||
| WWB15, | |||
| title | = | "{An FPT algorithm in polynomial space for the Directed Steiner Tree problem with Limited number of Diffusing nodes}", | |
| author | = | "D. Watel and M. Weisser and C. Bentz and D. Barth", | |
| journal | = | "Information processing letters", | |
| year | = | 2015, | |
| volume | = | 115, | |
| number | = | 2, | |
| pages | = | "275-279", | |
| doi | = | "10.1016/j.ipl.2014.09.027", | |
| } | |||
