Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions). (English) Zbl 1437.05220
Authors’ abstract: Given a vertex-weighted directed graph \(G=(V,E)\) and a set \(T=\{t_1, t_2, \dots, t_k\}\) of \(k\) terminals, the objective of the strongly connected Steiner subgraph (SCSS) problem is to find a vertex set \(H\subseteq V\) of minimum weight such that \(G[H]\) contains a \(t_i\rightarrow t_j\) path for each \(i\neq j\). The problem is NP-hard, but J. Feldman and M. Ruhl [SIAM J. Comput. 36, No. 2, 543–561 (2006; Zbl 1118.05039)] gave a novel \(n^{O(k)}\) algorithm for the SCSS problem, where \(n\) is the number of vertices in the graph and \(k\) is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a \(2^{O(k)}\cdot n^{O(\sqrt{k})}\) algorithm for planar SCSS, which is an improvement of a factor of \(O(\sqrt{k})\) in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an \(f(k)\cdot n^{o(\sqrt{k})}\) algorithm for any computable function \(f\), unless the exponential time hypothesis (ETH) fails. To obtain our algorithm, we first show combinatorially that there is a minimal solution whose treewidth is \(O(\sqrt{k})\), and then use the dynamic-programming based algorithm for finding bounded-treewidth solutions due to A. E. Feldmann and D. Marx [LIPIcs – Leibniz Int. Proc. Inform. 55, Article 27, 14 p. (2016; Zbl 1388.68228)]. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a gridlike fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: our \(2^{O(k)}\cdot n^{O(\sqrt{k})}\) algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. Additionally, we can obtain this running time for the problem of finding an optimal planar solution even if the input graph is not planar. In general graphs, we cannot hope for such a dramatic improvement over the \(n^{O(k)}\) algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an \(f(k)\cdot n^{o(k/\log k)}\) algorithm for any computable function \(f\). Feldman and Ruhl generalized their \(n^{O(k)}\) algorithm to the more general directed Steiner network (DSN) problem; here the task is to find a subgraph of minimum weight such that for every source \(s_i\) there is a path to the corresponding terminal \(t_i\). We show that, assuming ETH, there is no \(f(k)\cdot n^{o(k)}\) time algorithm for DSN on acyclic planar graphs. All our lower bounds hold for the integer weighted edge version, while the algorithm works for the more general unweighted vertex version.
Reviewer: Xueliang Li (Tianjin)
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68W40 | Analysis of algorithms |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C40 | Connectivity |
| 05C20 | Directed graphs (digraphs), tournaments |
Keywords:
strongly connected Steiner subgraph; FPT algorithms; directed Steiner network; exponential time hypothesis; planar graphsReferences:
| [1] | P. Aboulker, N. Brettell, F. Havet, D. Marx, and N. Trotignon, Coloring graphs with constraints on connectivity, J. Graph Theory, 85 (2017), pp. 814-838, https://doi.org/10.1002/jgt.22109. · Zbl 1368.05040 |
| [2] | M. Bateni, C. Chekuri, A. Ene, M. T. Hajiaghayi, N. Korula, and D. Marx, Prize-collecting Steiner problems on planar graphs, in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, CA, SIAM, Philadelphia, 2011, pp. 1028-1049, https://doi.org/10.1137/1.9781611973082.79. · Zbl 1376.68059 |
| [3] | M. Bateni, M. T. Hajiaghayi, and D. Marx, Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth, J. ACM, 58 (2011), 21, https://doi.org/10.1145/2027216.2027219. · Zbl 1281.68233 |
| [4] | P. Berman, A. Bhattacharyya, K. Makarychev, S. Raskhodnikova, and G. Yaroslavtsev, Approximation algorithms for spanner problems and directed Steiner forest, Inform. and Comput., 222 (2013), pp. 93-107, https://doi.org/10.1016/j.ic.2012.10.007. · Zbl 1267.68317 |
| [5] | A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Fourier meets Möbius: Fast subset convolution, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, CA, 2007, ACM, New York, 2007, pp. 67-74, https://doi.org/10.1145/1250790.1250801. · Zbl 1232.68188 |
| [6] | H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, and D. M. Thilikos, (Meta) Kernelization, J. ACM, 63 (2016), 44, https://doi.org/10.1145/2973749. · Zbl 1425.68137 |
| [7] | H. L. Bodlaender, D. Lokshtanov, and E. Penninkx, Planar capacitated dominating set is W[1]-hard, in Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, 2009, Revised Selected Papers, Springer, Berlin, 2009, pp. 50-60, https://doi.org/10.1007/978-3-642-11269-0_4. · Zbl 1273.68145 |
| [8] | É. Bonnet, P. Giannopoulos, and M. Lampis, On the parameterized complexity of red-blue points separation, in Proceedings of the 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, Wadern, Germany, Schloss Dagstuhl, Vienna, Austria, 2017, 8, https://doi.org/10.4230/LIPIcs.IPEC.2017.8. · Zbl 1423.68540 |
| [9] | É. Bonnet and T. Miltzow, Parameterized hardness of art gallery problems, in Proceedings of the 24th Annual European Symposium on Algorithms, ESA 2016, Aarhus, Denmark, Wadern, Germany, Schloss Dagstuhl, 2016, 19, https://doi.org/10.4230/LIPIcs.ESA.2016.19. · Zbl 1397.68091 |
| [10] | É. Bonnet and F. Sikora, The Graph Motif problem parameterized by the structure of the input graph, Discrete Appl. Math,, 231 (2017), pp. 78-94, https://doi.org/10.1016/j.dam.2016.11.016. · Zbl 1369.05195 |
| [11] | G. Borradaile, P. N. Klein, and C. Mathieu, An \(O(n \log n)\) approximation scheme for Steiner tree in planar graphs, ACM Trans. Algorithms, 5 (2009), 31, https://doi.org/10.1145/1541885.1541892. · Zbl 1300.05294 |
| [12] | K. Bringmann, L. Kozma, S. Moran, and N. S. Narayanaswamy, Hitting set for hypergraphs of low VC-dimension, in Proceedings of the 24th Annual European Symposium on Algorithms, ESA 2016, Aarhus, Denmark, Wadern, Germany, Schloss Dagstuhl, 2016, 23, https://doi.org/10.4230/LIPIcs.ESA.2016.23. · Zbl 1397.68092 |
| [13] | L. Cai, M. R. Fellows, D. W. Juedes, and F. A. Rosamond, The complexity of polynomial-time approximation, Theory Comput. Syst., 41 (2007), pp. 459-477, https://doi.org/10.1007/s00224-007-1346-y. · Zbl 1202.68481 |
| [14] | M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha, and M. Li, Approximation algorithms for directed Steiner problems, J. Algorithms, 33 (1999), pp. 73-91, https://doi.org/10.1006/jagm.1999.1042. · Zbl 0937.68155 |
| [15] | J. Chen, X. Huang, I. A. Kanj, and G. Xia, Strong computational lower bounds via parameterized complexity, J. Comput. System Sci., 72 (2006), pp. 1346-1367, https://doi.org/10.1016/j.jcss.2006.04.007. · Zbl 1119.68092 |
| [16] | R. Chitnis, H. Esfandiari, M. T. Hajiaghayi, R. Khandekar, G. Kortsarz, and S. Seddighin, A tight algorithm for strongly connected Steiner subgraph on two terminals with demands, Algorithmica, 77 (2017), pp. 1216-1239, https://doi.org/10.1007/s00453-016-0145-8. · Zbl 1364.68225 |
| [17] | R. Chitnis and A. E. Feldmann, FPT inapproximability of directed cut and connectivity problems, in Proceedings of the 14th International Symposium on Parmeterized and Exact Computation, IPEC 2019, Wadern, Germany, Schloss, Dagstuhl, 2019, 8, https://doi.org/10.4230/LIPIcs.IPEC.2019.8. · Zbl 07650216 |
| [18] | R. Chitnis, A. E. Feldmann, and P. Manurangsi, Parameterized approximation algorithms for bidirected Steiner network problems, in Proceedings of the 26th Annual European Symposium on Algorithms, ESA 2018, Helsinki, Finland, Denmark, Wadern, Germany, Schloss Dagstuhl, 2018, 20, https://doi.org/10.4230/LIPIcs.ESA.2018.20. · Zbl 1522.68395 |
| [19] | R. H. Chitnis, M. Hajiaghayi, and D. Marx, Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions), in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, 2014, SIAM, Philadelphia, 2014, pp. 1782-1801, https://doi.org/10.1137/1.9781611973402.129. · Zbl 1421.68112 |
| [20] | R. Curticapean, H. Dell, and D. Marx, Homomorphisms are a good basis for counting small subgraphs, in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, 2017, ACM, New York, pp. 210-223, https://doi.org/10.1145/3055399.3055502. · Zbl 1369.05191 |
| [21] | R. Curticapean and D. Marx, Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts, in Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, IEEE, Piscataway, NJ, 2014, pp. 130-139, https://doi.org/10.1109/FOCS.2014.22. |
| [22] | R. Curticapean and M. Xia, Parameterizing the permanent: Genus, apices, minors, evaluation mod 2k, in Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, IEEE, Piscataway, NJ, 2015, pp. 994-1009, https://doi.org/10.1109/FOCS.2015.65. |
| [23] | M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Parameterized Algorithms, Springer, Cham, Switzerland, 2015, https://doi.org/10.1007/978-3-319-21275-3. · Zbl 1334.90001 |
| [24] | E. D. Demaine, F. V. Fomin, M. T. Hajiaghayi, and D. M. Thilikos, Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs, J. ACM, 52 (2005), pp. 866-893, https://doi.org/10.1145/1101821.1101823. · Zbl 1326.05152 |
| [25] | E. D. Demaine and M. Hajiaghayi, The bidimensionality theory and its algorithmic applications, Comput. J., 51 (2008), pp. 292-302, https://doi.org/10.1093/comjnl/bxm033. |
| [26] | E. D. Demaine and M. T. Hajiaghayi, Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality, in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, SIAM, Philadelphia, 2005, pp. 682-689, http://dl.acm.org/citation.cfm?id=1070432.1070528. · Zbl 1297.05227 |
| [27] | E. D. Demaine, M. T. Hajiaghayi, and P. N. Klein, Node-weighted Steiner tree and group Steiner tree in planar graphs, ACM Trans. Algorithms, 10 (2014), 13, https://doi.org/10.1145/2601070. · Zbl 1398.68667 |
| [28] | R. G. Downey and M. R. Fellows, Parameterized Complexity, Monogr. Comput. Sci., Springer, New York, 1999, https://doi.org/10.1007/978-1-4612-0515-9. |
| [29] | S. E. Dreyfus and R. A. Wagner, The Steiner problem in graphs, Networks, 1 (1971), pp. 195-207, https://doi.org/10.1002/net.3230010302. · Zbl 0229.05125 |
| [30] | P. Dvorák, A. E. Feldmann, D. Knop, T. Masarík, T. Toufar, and P. Veselý, Parameterized approximation schemes for Steiner trees with small number of Steiner vertices, in Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, Caen, France, Wadern, Germany, Schloss Dagstuhl, 2018, 26, https://doi.org/10.4230/LIPIcs.STACS.2018.26. · Zbl 1487.68175 |
| [31] | E. Eiben, D. Knop, F. Panolan, and O. Suchý, Complexity of the Steiner network problem with respect to the number of terminals, in 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, Berlin, Germany, Wadern, Germany, Schloss Dagstuhl, 2019, 25, https://doi.org/10.4230/LIPIcs.STACS.2019.25. · Zbl 07559134 |
| [32] | D. Eisenstat, P. Klein, and C. Mathieu, An efficient polynomial-time approximation scheme for Steiner forest in planar graphs, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, SIAM, Philadelphia, 2012, pp. 626-638, https://doi.org/10.1137/1.9781611973099.53. · Zbl 1421.68214 |
| [33] | R. Enciso, M. R. Fellows, J. Guo, I. A. Kanj, F. A. Rosamond, and O. Suchý, What makes equitable connected partition easy, in Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, 2009, Revised Selected Papers, Springer, Berlin, 2009, pp. 122-133, https://doi.org/10.1007/978-3-642-11269-0_10. · Zbl 1273.68164 |
| [34] | D. Eppstein and D. Lokshtanov, The parameterized complexity of finding point sets with hereditary properties, in Proceedings of the 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, Helsinki, Finland, Wadern, Germany, Schloss Dagstuhl, 2018, 11, https://doi.org/10.4230/LIPIcs.IPEC.2018.11. · Zbl 1520.68048 |
| [35] | J. Feldman and M. Ruhl, The directed Steiner network problem is tractable for a constant number of terminals, SIAM J. Comput., 36 (2006), pp. 543-561, https://doi.org/10.1137/S0097539704441241. · Zbl 1118.05039 |
| [36] | A. E. Feldmann and D. Marx, The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems, https://arxiv.org/abs/1707.06808, 2017. · Zbl 1388.68228 |
| [37] | J. Flum and M. Grohe, Parameterized Complexity Theory, Texts Theoret. Comput. Sci. EATCS Ser., Springer, Berlin, 2006, https://doi.org/10.1007/3-540-29953-X. · Zbl 1143.68016 |
| [38] | F. V. Fomin, S. Kolay, D. Lokshtanov, F. Panolan, and S. Saurabh, Subexponential algorithms for rectilinear Steiner tree and arborescence problems, in Proceedings of the 32nd International Symposium on Computational Geometry, SoCG 2016, Boston, MA, Wadern, Germany, Schloss Dagstuhl, 2016, 39, https://doi.org/10.4230/LIPIcs.SoCG.2016.39. · Zbl 1387.68180 |
| [39] | F. V. Fomin, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering, in Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, New Brunswick, NJ, IEEE, Piscataway, NJ, 2016, pp. 515-524, https://doi.org/10.1109/FOCS.2016.62. · Zbl 1511.05222 |
| [40] | M. Frick and M. Grohe, Deciding first-order properties of locally tree-decomposable structures, J. ACM, 48 (2001), pp. 1184-1206, https://doi.org/10.1145/504794.504798. · Zbl 1323.03014 |
| [41] | J. Guo, S. Hartung, R. Niedermeier, and O. Suchý, The parameterized complexity of local search for TSP, more refined, Algorithmica, 67 (2013), pp. 89-110, https://doi.org/10.1007/s00453-012-9685-8. · Zbl 1292.68086 |
| [42] | J. Guo, R. Niedermeier, and O. Suchý, Parameterized complexity of arc-weighted directed Steiner problems, SIAM J. Discrete Math., 25 (2011), pp. 583-599, https://doi.org/10.1137/100794560. · Zbl 1230.05268 |
| [43] | S. L. Hakimi, Steiner’s problem in graphs and its implications, Networks, 1 (1971), pp. 113-133, https://doi.org/10.1002/net.3230010203. · Zbl 0229.05124 |
| [44] | E. Halperin and R. Krauthgamer, Polylogarithmic inapproximability, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, San Diego, CA, ACM, New York, 2003, pp. 585-594, https://doi.org/10.1145/780542.780628. · Zbl 1192.68321 |
| [45] | R. Impagliazzo and R. Paturi, On the Complexity of \(k\)-SAT, J. Comput. System Sci., 62 (2001), pp. 367-375, https://doi.org/10.1006/jcss.2000.1727. · Zbl 0990.68079 |
| [46] | R. Impagliazzo, R. Paturi, and F. Zane, Which problems have strongly exponential complexity?, J. Comput. System Sci., 63 (2001), pp. 512-530, https://doi.org/10.1006/jcss.2001.1774. · Zbl 1006.68052 |
| [47] | K. Jansen, S. Kratsch, D. Marx, and I. Schlotter, Bin packing with fixed number of bins revisited, J. Comput. System Sci., 79 (2013), pp. 39-49, https://doi.org/10.1016/j.jcss.2012.04.004. · Zbl 1261.68065 |
| [48] | M. Jones, D. Lokshtanov, M. S. Ramanujan, S. Saurabh, and O. Suchý, Parameterized complexity of directed Steiner tree on sparse graphs, SIAM J. Discrete Math., 31 (2017), pp. 1294-1327, https://doi.org/10.1137/15M103618X. · Zbl 1371.68115 |
| [49] | R. M. Karp, Reducibility among combinatorial problems, in Proceedings of a Symposium on the Complexity of Computer Computations, 1972, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, Springer, Boston, 1972, pp. 85-103, https://doi.org/10.1007/978-1-4684-2001-2_9. · Zbl 1467.68065 |
| [50] | P. N. Klein and D. Marx, Solving planar \(k\)-terminal cut in \(O(n^{c \sqrt{k}})\) time, in Automata, Languages, and Programming, 39th International Colloquium, ICALP 2012, Warwick, UK, Part I, Springer, Berlin, 2012, pp. 569-580, https://doi.org/10.1007/978-3-642-31594-7_48. · Zbl 1272.68157 |
| [51] | P. N. Klein and D. Marx, A subexponential parameterized algorithm for subset TSP on planar graphs, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, SIAM, Philadelphia, 2014, pp. 1812-1830, https://doi.org/10.1137/1.9781611973402.131. · Zbl 1423.68214 |
| [52] | A. Levin, Algorithm for the shortest connection of a group of graph vertices, Sov. Math. Dokl., 12 (1971), pp. 1477-1481. · Zbl 0243.05119 |
| [53] | C. Li, S. T. McCormick, and D. Simchi-Levi, The point-to-point delivery and connection problems: Complexity and algorithms, Discrete Appl. Math., 36 (1992), pp. 267-292, https://doi.org/10.1016/0166-218X(92)90258-C. · Zbl 0761.68022 |
| [54] | D. Lokshtanov, M. S. Ramanujan, S. Saurabh, and M. Zehavi, Parameterized Complexity and Approximability of Directed Odd Cycle Transversal, in Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, SIAM, Philadelphia, 2020, pp. 2181-2200, https://doi.org/10.1137/1.9781611975994.134. · Zbl 07304158 |
| [55] | D. Lokshtanov, S. Saurabh, and M. Wahlström, Subexponential parameterized odd cycle transversal on planar graphs, in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, Hyderabad, India, Wadern, Germany, Schloss Dagstuhl, 2012, pp. 424-434, https://doi.org/10.4230/LIPIcs.FSTTCS.2012.424. · Zbl 1354.68129 |
| [56] | D. Marx, On the optimality of planar and geometric approximation schemes, in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007, Providence, RI, IEEE Computer Society, Los Alamitos, CA, 2007, pp. 338-348. |
| [57] | D. Marx, Can you beat treewidth?, Theory Comput., 6 (2010), pp. 85-112, https://doi.org/10.4086/toc.2010.v006a005. · Zbl 1213.68316 |
| [58] | D. Marx, A tight lower bound for planar multiway cut with fixed number of terminals, in Automata, Languages, and Programming, 39th International Colloquium, ICALP 2012, Warwick, UK, 2012, Part I, Springer, Berlin, 2012, pp. 677-688, https://doi.org/10.1007/978-3-642-31594-7_57. · Zbl 1272.68147 |
| [59] | D. Marx and M. Pilipczuk, Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams, in Algorithms, ESA 2015, Proceedings of the 23rd Annual European Symposium, Patras, Greece, Springer, Berlin, 2015, pp. 865-877, https://doi.org/10.1007/978-3-662-48350-3_72. · Zbl 1422.68253 |
| [60] | D. Marx, M. Pilipczuk, and M. Pilipczuk, On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs, in Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, IEEE, Piscataway, NJ, 2018, pp. 474-484, https://doi.org/10.1109/FOCS.2018.00052. |
| [61] | M. Natu and S. Fang, The Point-to-point connection problem-Analysis and algorithms, Discrete Appl. Math., 78 (1997), pp. 207-226, https://doi.org/10.1016/S0166-218X(97)00010-3. · Zbl 0890.68104 |
| [62] | R. Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford University Press, Oxford, 2006, https://doi.org/10.1093/ACPROF:OSO/9780198566076.001.0001. · Zbl 1095.68038 |
| [63] | M. Pilipczuk, M. Pilipczuk, P. Sankowski, and E. J. van Leeuwen, Subexponential-time parameterized algorithm for Steiner tree on planar graphs, in Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, Kiel, Germany, Wadern, Germany, Schloss, Dagstuhl, 2013, pp. 353-364, https://doi.org/10.4230/LIPIcs.STACS.2013.353. · Zbl 1354.68132 |
| [64] | M. Pilipczuk and M. Wahlström, Directed multicut is \(W[1]\)-hard, even for four terminal pairs, ACM Trans. Comput. Theory, 10 (2018), pp. 13, https://doi.org/10.1145/3201775. · Zbl 1427.68252 |
| [65] | S. Ramanathan, Multicast tree generation in networks with asymmetric links, IEEE/ACM Trans. Netw., 4 (1996), pp. 558-568, https://doi.org/10.1109/90.532865. |
| [66] | N. Robertson, P. D. Seymour, and R. Thomas, Quickly excluding a planar graph, J. Combin. Theory Ser. B, 62 (1994), pp. 323-348, https://doi.org/10.1006/jctb.1994.1073. · Zbl 0807.05023 |
| [67] | H. F. Salama, D. S. Reeves, and Y. Viniotis, Evaluation of multicast routing algorithms for real-time communication on high-speed networks, IEEE J. Sel. Areas Commun., 15 (1997), pp. 332-345, https://doi.org/10.1109/49.564132. |
| [68] | O. Suchý, On directed Steiner trees with multiple roots, in Graph-Theoretic Concepts in Computer Science, 42nd International Workshop, WG 2016, Istanbul, Turkey, Revised Selected Papers, Springer, Berlin, 2016, pp. 257-268, https://doi.org/10.1007/978-3-662-53536-3_22. · Zbl 1417.05089 |
| [69] | P. Winter, Steiner problem in networks: A survey, Networks, 17 (1987), pp. 129-167, https://doi.org/10.1002/net.3230170203. · Zbl 0646.90028 |
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.
