Directed Steiner Tree with Branching Constraint

Abstract : Given a directed weighted graph G, a root r and k terminals, the k-Directed Steiner Tree problem is to find a minimum cost tree rooted at r and spanning all terminals. If this problem has several applications in multicast routing in packet switching networks, the modeling is not adapted anymore in networks based upon the circuit switching principle in which some nodes, called non diffusing nodes, are not able to duplicate packets. We define a more general problem, named Directed Steiner Tree with Limited number of Diffusing nodes (DSTLD), able to model the multicast in a network containing at most d diffusing nodes. We show that DSTLD is XP with respect to d, and use this result to build a ⌈k−1d⌉ -approximation XP in d for DST. Finally, we prove that, under the assumption that NP ⊈ DTIME[n O(loglogn)], there is no polynomial approximation algorithm for DSTLD with ratio 1+(1e−ε)⋅kd−1 for every constant ε > 0.
Type de document :
Communication dans un congrès
Eds. Zhipeng Cai, Alex Zelikovsky and Anu Bourgeois. 20th International Computing and Combinatorics Conference - COCOON, Aug 2014, Atlanta, United States. Springer, LNCS 8591, pp.263-275, 2014, 〈10.1007/978-3-319-08783-2_23〉
Liste complète des métadonnées

https://hal-supelec.archives-ouvertes.fr/hal-01067142
Contributeur : Elodie Dubrac <>
Soumis le : mardi 23 septembre 2014 - 09:32:44
Dernière modification le : mardi 13 novembre 2018 - 17:10:02

Identifiants

Collections

Citation

Dimitri Watel, Marc-Antoine Weisser, Cédric Bentz, Dominique Barth. Directed Steiner Tree with Branching Constraint. Eds. Zhipeng Cai, Alex Zelikovsky and Anu Bourgeois. 20th International Computing and Combinatorics Conference - COCOON, Aug 2014, Atlanta, United States. Springer, LNCS 8591, pp.263-275, 2014, 〈10.1007/978-3-319-08783-2_23〉. 〈hal-01067142〉

Partager

Métriques

Consultations de la notice

181