×

The clustered selected-internal Steiner tree problem. (English) Zbl 1522.68393

Summary: Given a complete graph \(G=(V,E)\), with nonnegative edge costs, two subsets \(R\subset V\) and \(R'\subset R\), a partition \(\mathcal{R}=\{R_1, R_2,\dots,R_k\}\) of \(R\), \(R_i\cap R_j=\emptyset\), \(i\neq j\) and \(\mathcal{R}'=\{R_1', R_2',\dots,R_k'\}\) of \(R'\), \(R_i'\subset R_i\), a clustered Steiner tree is a tree \(T\) of \(G\) that spans all vertices in \(R\) such that \(T\) can be cut into \(k\) subtrees \(T_i\) by removing \(k-1\) edges and each subtree \(T_i\) spans all vertices in \(R_i\), \(1\leq i\leq k\). The cost of a clustered Steiner tree is defined to be the sum of the costs of all its edges. A clustered selected-internal Steiner tree of \(G\) is a clustered Steiner tree for \(R\) if all vertices in \(R_i^\prime\) are internal vertices of \(T_i\). The clustered selected-internal Steiner tree problem is concerned with the determination of a clustered selected-internal Steiner tree \(T\) for \(R\) and \(R'\) in \(G\) with minimum cost. In this paper, we present the first known approximation algorithm with performance ratio \((\rho+4)\) for the clustered selected-internal Steiner tree problem, where \(\rho\) is the best-known performance ratio for the Steiner tree problem.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68W25 Approximation algorithms

References:

[1] Bao, X. and Liu, Z., An improved approximation algorithm for the clustered traveling salesman problem, Informa. Process. Lett.112 (2012) 908-910. · Zbl 1248.68551
[2] Berman, P. and Ramaiyer, V., Improved approximations for the Steiner tree problem, J. Algorithms17 (1994) 381-408. · Zbl 0820.68049
[3] Bern, M. and Plassmann, P., The Steiner tree problem with edge lengths 1 and 2, Inform. Process. Lett.32 (1989) 171-176. · Zbl 0677.68074
[4] Borchers, A. and Du, D. Z., The \(k\)-Steiner ratio in graphs, SIAM J. Comput.26 (1997) 857-869. · Zbl 0870.68109
[5] Byrka, J., Grandoni, F., Rothvos, T. and Sanita, L., Steiner tree approximation via iterative randomized rounding, J. Assoc. Comput. Mach.60 (2013) 6. · Zbl 1281.68234
[6] Caldwell, A., Kahng, A., Mantik, S., Markov, I. and Zelikovsky, A., On wirelength estimations for row-based placement, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems18(9) (1999) 1265-1278.
[7] Chen, Y. H., The bottleneck selected-internal and partial terminal Steiner tree problems, Networks68(4) (2016) 331-339. · Zbl 1390.90101
[8] Cheng, X. and Du, D. Z., Steiner Trees in Industry (Kluwer Academic Publishers, Dordrecht, Netherlands, 2001).
[9] Chisman, J. A., The clustered traveling salesman problem, Comput. Operat. Res. (1975) 115-119.
[10] Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C., Introduction to Algorithm, 3rd edition (MIT Press, Cambridge, 2009). · Zbl 1187.68679
[11] Ding, C., Cheng, Y. and He, M., Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPs, Tsinghua Sci. Technol.12 (2007) 459-465. · Zbl 1174.90863
[12] Drummond, L. M. A. and Santos, M., A distributed dual ascent algorithm for Steiner problems in multicast routing, Networks53 (2009) 170-183. · Zbl 1192.68821
[13] Du, D. Z., Smith, J. M. and Rubinstein, J. H., Advance in Steiner Tree (Kluwer Academic Publishers, Dordrecht, Netherlands, 2000). · Zbl 0932.00010
[14] Du, D. Z. and Hu, X., Steiner Tree Problems in Computer Communication Networks (World Scientific Publishing Company, 2008). · Zbl 1156.90014
[15] Garey, M., Graham, R. and Johnson, D., The complexity of computing Steiner minimal trees, SIAM J. Appl. Math.32 (1977) 835-859. · Zbl 0399.05023
[16] Golovnev, A., Approximating asymmetric tsp in exponential time, Int. J. Found. Comput. Sci.25(1) (2014) 89-99. · Zbl 1291.68177
[17] Graur, D. and Li, W. H., Fundamentals of Molecular Evolution, 2nd edition (Sinauer Publishers, Sunderland, MA, 2000).
[18] Guttmann-beck, N., Hassin, R., Khuller, S. and Raghavachari, B., Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem, Algorithmica28 (2000) 422-437. · Zbl 0963.68226
[19] Hougardy, S. and Promel, H. J., A 1.598 approximation algorithm for the Steiner tree problem in graphs, Proc. 10th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA) (Baltimore, USA, , 1999), pp. 448-453. · Zbl 0946.68107
[20] Hougardy, S. and Kirchner, S., Lower bounds for the relative greedy algorithm for approximating Steiner trees, Networks47 (2006) 111-115. · Zbl 1129.90057
[21] Hsieh, S. Y. and Yang, S. C., Approximating the selected-internal Steiner tree, Theoret. Comput. Sci.381 (2007) 288-291. · Zbl 1188.68356
[22] Hwang, F. K., Richards, D. S. and Winter, P., The Steiner Tree Problem, in , Vol. 53 (Elsevier Science Publishers, Amsterdam, 1992). · Zbl 0774.05001
[23] Karaganis, J. J., On the cube of a graph, Canadian Math. Bull.11 (1968) 295-296. · Zbl 0162.27701
[24] Laporte, G., Potvin, J. Y. and Quilleret, F., A Tabu search heuristic using genetic diversification for the clustered traveling salesman problem, J. Heuristics2 (1995) 187-200.
[25] Li, X., Zou, F., Huang, Y., Kim, D. and Wu, W., A better constant-factor approximation for selected-internal Steiner minimum tree, Algorithmica56 (2010) 333-341. · Zbl 1187.68713
[26] Prim, R. C., Shortest connection networks and some generalizations, Bell Syst. Tech. J.36 (1957) 1389-1401.
[27] Prommel, H. J. and Steger, A., A new approximation algorithm for the Steiner tree problem with performance ratio 5/3, J. Algorithms36 (2000) 89-101. · Zbl 0959.68101
[28] Robins, G. and Zelikovsky, A., Tighter bounds for graph Steiner tree approximation, SIAM J. Discr. Math.19 (2005) 122-134. · Zbl 1082.05088
[29] Saikia, P. and Karmakar, S., Distributed approximation algorithms for Steiner tree in the congested clique, Int. J. Found. Comput. Sci.31(7) (2020) 941-968. · Zbl 1458.68278
[30] Sekanina, M., On an ordering of the set of vertices of a connected graph, Publ. Faculty of Science, University of Brno412 (1960) 137-141. · Zbl 0118.18903
[31] Winter, P., Steiner problem in networks: A survey, Networks17 (1987) 129-167. · Zbl 0646.90028
[32] Wu, B. Y. and Lee, C. W., On the clustered Steiner tree problem, J. Combin. Optim.30 (2015) 370-386. · Zbl 1327.90271
[33] Zelikovsky, A., An 11/6-approximation algorithm for the network Steiner problem, Algorithmica9 (1993) 463-470. · Zbl 0768.68192
[34] Zelikovsky, A., A faster approximation algorithm for the Steiner tree problem in graphs, Inform. Process. Lett.46 (1993) 79-83. · Zbl 0770.68078
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.