Directed Steiner trees with diffusion costs

Dimitri Watel (), Marc-Antoine Weisser (), Cédric Bentz () and Dominique Barth ()
Additional contact information
Dimitri Watel: SUPELEC System Sciences
Marc-Antoine Weisser: SUPELEC System Sciences
Cédric Bentz: CEDRIC-CNAM
Dominique Barth: University of Versailles

Journal of Combinatorial Optimization, 2016, vol. 32, issue 4, No 8, 1089-1106

Abstract: Abstract Given a directed arc-weighted graph G with n nodes, a root r and k terminals, the directed steiner tree problem (DST) consists in finding a minimum-weight tree rooted at r and spanning all the 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 unable to duplicate packets. We define a more general problem, namely the directed steiner tree with a limited number of diffusing nodes (DSTLD), that enables us to model 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 $$\left\lceil \frac{k-1}{d} \right\rceil $$ k - 1 d -approximation algorithm for DST that is XP in d. We deduce from that result a strong inapproximability property. In particular, we prove that, under the assumption that NP $$\not \subseteq $$ ⊈ ZTIME $$[n^{\log ^{O(1)}n}]$$ [ n log O ( 1 ) n ] , there is no polynomial-time approximation algorithm for DSTLD with ratio $$\varOmega \left( \frac{k}{d}\right) $$ Ω k d . We finally give an evaluation of performances of an exact algorithm dedicated to the case $$d \le 3$$ d ≤ 3 .

Keywords: Approximation; Parameterized complexity; Directed steiner tree; Diffusing node (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9925-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:4:d:10.1007_s10878-015-9925-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9925-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().