×

Directed Steiner trees with diffusion costs. (English) Zbl 1356.90152

Summary: 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 \)-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}]\), there is no polynomial-time approximation algorithm for DSTLD with ratio \(\varOmega \left( \frac{k}{d}\right) \). We finally give an evaluation of performances of an exact algorithm dedicated to the case \(d \leq 3\).

MSC:

90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Charikar M, Chekuri C, Cheung T, Dai Z (1998) Approximation algorithms for directed Steiner problems. In: Proceedings of SODA, pp 192-200 · Zbl 0930.68107
[2] Cheng X, Du D-Z (2001) Steiner trees in industry, vol 11. Kluwer, Dordrecht · Zbl 1179.90277
[3] Ding B, Yu JX, Wang S, Qin L (2007) Finding top-k min-cost connected trees in databases. In: ICDE, pp 836-845 · Zbl 1017.90090
[4] Downey R, Fellows M (1999) Parameterized complexity. Monographs in computer science. Springer, Berlin · doi:10.1007/978-1-4612-0515-9
[5] Dreyfus SE, Wagner RA (1971) The Steiner problem in graphs. Networks 1(3):195-207 · Zbl 0229.05125 · doi:10.1002/net.3230010302
[6] Du H, Jia X, Wang F, Thai MY, Li Y (2005) A note on optical network with nonsplitting nodes. JCO 10:199-202 · Zbl 1093.90068
[7] Feige U (1998) A threshold of ln n for approximating set cover. JACM 45(4):634-652 · Zbl 1065.68573 · doi:10.1145/285055.285059
[8] Floyd R (1962) Algorithm 97: shortest path. Commun ACM 5(6):345 · doi:10.1145/367766.368168
[9] Gargano L, Hell P, Stacho L, Vaccaro U (2002) Spanning trees with bounded number of branch vertices. In: Proceedings of ICALP, pp 355-365 · Zbl 1056.68587
[10] Guo L, Wu W, Wang F, Thai M (2005) An approximation for minimum multicast route in optical networks with nonsplitting nodes. J Comb Optim 10(4):391-394 · Zbl 1078.05079 · doi:10.1007/s10878-005-4925-3
[11] Halperin E, Krauthgamer R (2003) Polylogarithmic inapproximability. In Proceedings of the 35th ACM symposium on theory of computing (STOC), ACM, New York, pp 585-594 · Zbl 1192.68321
[12] Helvig CS, Robins G, Zelikovsky A (2001) An improved approximation scheme for the group Steiner problem. Networks 37(1):8-20 · Zbl 0997.90096 · doi:10.1002/1097-0037(200101)37:1<8::AID-NET2>3.0.CO;2-R
[13] Jones M, Lokshtanov D, Ramanujan M, Saurabh S, Suchy O (2013) Parameterized complexity of directed Steiner tree on sparse graphs. In: Proceedings of ESA, pp 671-682 · Zbl 1371.68114
[14] Karp R (1972) Reducibility among combinatorial problems. In: Complexity of computer computations. The IBM research symposia series, Springer, New York, pp 85-103 · Zbl 1467.68065
[15] Koch T, Martin A, Voß S (2001) SteinLib: an updated library on Steiner tree problems in graphs. In: Combinatorial optimization, vol 11, Springer, New York, pp 285-325
[16] Kou L, Markowsky G, Berman L (1981) A fast algorithm for Steiner trees. Acta Inf 15:141-145 · Zbl 0445.68051 · doi:10.1007/BF00288961
[17] Lin H-c, Wang S-w (2005) Splitter placement in all-optical WDM networks. Global telecommunications conference · Zbl 0997.90096
[18] Malli R, Zhang X, Qiao C (1998) Benefit of multicasting in all-optical networks. In: Proceedings of the SPIE conference on all-optical networking
[19] Novak R (2001) A note on distributed multicast routing in point-to-point networks. Comput Oper Res 28(12):1149-1164 · Zbl 1017.90090 · doi:10.1016/S0305-0548(00)00029-0
[20] Reinhard V, Cohen J, Tomasik J, Barth D, Weisser M-A (2012) Optimal configuration of an optical network providing predefined multicast transmissions. Comput Netw 56(8):2097-2106 · doi:10.1016/j.comnet.2012.02.005
[21] Reinhard V, Tomasik J, Barth D, Weisser M-A (2009) Bandwidth optimization for multicast transmissions in virtual circuit networks. IFIP networking, pp 859-870
[22] Robins G, Zelikovsky A (2000) Improved Steiner tree approximation in graphs. In Proceedings of the SODA, pp 770-779 · Zbl 0957.68084
[23] Rugeli J, Novak R (1995) Steiner tree algorithms for multicast protocols. Manuscript
[24] Salazar-González J-J (2003) The Steiner cycle polytope. Eur J Oper Res 147(3):671-679 · Zbl 1031.90028 · doi:10.1016/S0377-2217(02)00359-4
[25] Steinová M (2010) Approximability of the minimum Steiner cycle problem. Comput Inform 29:1349-1357 · Zbl 1399.68077
[26] Tarjan R (1977) Finding optimum branchings. Networks 7(1):25-35 · Zbl 0379.90100 · doi:10.1002/net.3230070103
[27] Voß S (2006) Steiner tree problems in telecommunications. In: Handbook of optimization in telecommunications, Springer, New York, pp 459-492 · Zbl 1118.90025
[28] Watel D, Weisser M, Bentz C, Barth D (2013) Steiner problems with limited number of branching nodes. In: Proceedings of SIROCCO, pp 310-321 · Zbl 1406.68092
[29] Watel D, Weisser M, Bentz C, Barth D (2014) Directed Steiner tree with branching constraint. In: Proceedings of COCOON, pp 263-275 · Zbl 1423.68359
[30] Zelikovsky A (1997) A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica 18(1):99-110 · Zbl 0873.68079 · doi:10.1007/BF02523690
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.