Given a directed graph with weights on the arcs, a special node called the root and a set of nodes called the terminals, the directed Steiner Tree problem (DST) consists in the search of a minimum cost tree rooted at the root and spanning all the terminals. For example, on the right, where every weight is 1, an optimal directed Steiner tree links the root
r to the terminals
a, b, c with 5 arcs. This problem can be used for example to build a multicast diffusion tree in a network.
We were interested here in building polynomial approximation algorithms for this problem. The best known approximation ratio is O(kε), for every constant ε > 0. However, in practice, this approximation is not used due to a prohibitive running time. A simpler k-approximation algorithm is used instead and consists in returning the union of shortest paths from the root to each terminal.
|
[WWBB15b]
|
D. Watel, M.-A. Weisser, C. Bentz, and D. Barth.
An FPT algorithm in polynomial space for the directed steiner tree
problem with limited number of diffusing nodes.
Information Processing Letters, 115(2):275 -- 279, 2015.
[ DOI |
http ]
|
|
[WWBB15a]
|
D. Watel, M.-A. Weisser, C. Bentz, and D. Barth.
Directed steiner trees with diffusion costs.
Journal of Combinatorial Optimization (Version longue de
[WWBB14]), pages 1--18, 2015.
[ DOI |
http ]
|
|
[WW16]
|
Dimitri Watel and Marc-Antoine Weisser.
A practical greedy approximation for the directed steiner tree
problem.
Journal of Combinatorial Optimization (Version longue de
[WW14b]), 32(4):1327--1370, 2016.
[ DOI |
http ]
|
|
[WWBB13]
|
D. Watel, M.-A. Weisser, C. Bentz, and D. Barth.
Steiner problems with limited number of branching nodes.
In Structural Information and Communication Complexity - 20th
International Colloquium, SIROCCO 2013, rang B, 41.8%, Ischia, Italy, July
1-3, 2013, Revised Selected Papers, pages 310--321, 2013.
[ DOI |
http ]
|
|
[WWBB14]
|
D. Watel, M.-A. Weisser, C. Bentz, and D. Barth.
Directed steiner tree with branching constraint.
In Computing and Combinatorics - 20th International Conference,
COCOON 2014, Rang A, 46.4%, Atlanta, GA, USA, August 4-6, 2014.
Proceedings, pages 263--275, 2014.
[ DOI |
http ]
|
|
[WW14b]
|
D. Watel and M.-A. Weisser.
A practical greedy approximation for the directed steiner tree
problem.
In Combinatorial Optimization and Applications - 8th
International Conference, COCOA 2014, rang B, 42.1%, Wailea, Maui, HI,
USA, December 19-21, 2014, Proceedings, pages 200--215, 2014.
[ DOI |
http ]
|
|
[WW14a]
|
D. Watel and M.-A. Weisser.
Le problème de l'arborescence de Steiner dans les réseaux
tout-optiques.
In ALGOTEL 2014 -- 16èmes Rencontres Francophones sur les
Aspects Algorithmiques des Télécommunications, pages 1--4, Le
Bois-Plage-en-Ré, France, June 2014.
[ http |
.pdf ]
|