PRUNING MINIMUM SPANNING TREES AND CUTTING LONGEST EDGES TO CONNECT A GIVEN NUMBER OF NODES BY MINIMIZING TOTAL EDGE LENGTH
DOI:
https://doi.org/10.20535/2411-2976.22023.40-52Keywords:
minimum spanning tree, triangulation, edge lengths, pruning the tree, cutting longest edgesAbstract
Background. Whereas in many tasks of designing efficient telecommunication networks, the number of network nodes is limited, the initial choice of nodes is wider. There are more possible locations than factually active tools to be settled to those locations to further satisfy consumers. This induces an available node constraint problem.
Objective. Given an initial set of planar nodes, the problem is to build a minimum spanning tree connecting a given number of the nodes, which is less than the cardinality of the initial set. Therefore, the available node constraint problem aims at building an optimally minimum spanning tree to connect a given number of planar nodes being less than an initial number of nodes by minimizing the tree length.
Methods. The initial set of nodes is triangulated. This gives a set of edges, whose lengths are calculated and used as graph weights. A minimum spanning tree is built over this graph. The desired number of nodes is reached by pruning the minimum spanning tree connecting the initial number of nodes, where free edges whose weights are the largest are iteratively removed from the tree. The other approach, the cutting method, removes longest edges off the initial minimum spanning tree, regardless of whether they are free or not.
Results. Unlike the pruning method, the method of cutting longest edges may result in a minimum spanning tree connecting fewer nodes than the desired number. However, the cutting method often outputs a shorter tree, especially when the edge length varies much. Besides, the cutting method is slower due to it iteratively rebuilds a minimum spanning tree.
Conclusions. The problem is initially solved by the pruning method. Then the cutting method is used and its solution is compared to the solution by the pruning method. The best tree is shorter. A tradeoff for the nodes and tree length is possible.
References
H. Loberman and A. Weinberger, “Formal procedures for connecting terminals with a minimum total wire length,” Journal of the ACM, vol. 4, iss. 4, pp. 428 — 437, 1957. https://doi.org/10.1145/320893.320896
V. V. Romanuke, “Fast-and-smoother uplink power control algorithm based on distance ratios for wireless data transfer systems,” Studies in Informatics and Control, vol. 28, iss. 2, pp. 147 — 156, 2019. https://doi.org/10.24846/v28i2y201903
H. Ahmadi and J. R. Martí, “Minimum-loss network reconfiguration: A minimum spanning tree problem,” Sustainable Energy, Grids and Networks, vol. 1, pp. 1 — 9, 2015. https://doi.org/10.1016/j.segan.2014.10.001
B. Stojanović, T. Rajić, and D. Šošić, “Distribution network reconfiguration and reactive power compensation using a hybrid Simulated Annealing — Minimum spanning tree algorithm,” International Journal of Electrical Power & Energy Systems, vol. 147, Article ID 108829, 2023. https://doi.org/10.1016/j.ijepes.2022.108829
V. V. Romanuke, “Building minimum spanning trees by limited number of nodes over triangulated set of initial nodes,” Information and Telecommunication Sciences, vol. 14, no. 1, pp. 41 — 50, 2023.
J. A. De Loera, J. Rambau, and F. Santos, Triangulations, Structures for Algorithms and Applications, in Algorithms and Computation in Mathematics, vol. 25, Springer, 2010.
H. Edelsbrunner, T. S. Tan, and R. Waupotitsch, “An time algorithm for the minmax angle triangulation,” SIAM Journal on Scientific and Statistical Computing, vol. 13, iss. 4, pp. 994 — 1008, 1992. https://doi.org/10.1137/0913058
G. Xia, “The stretch factor of the Delaunay triangulation is less than 1.998,” SIAM Journal on Computing, vol. 42, iss. 4, pp. 1620 — 1659, 2013.
https://doi.org/10.1137/110832458
T. Biedl, G. Kant, and M. Kaufmann, “On triangulating planar graphs under the four-connectivity constraint,” Algorithmica, vol. 19, pp. 427 — 446, 1997.
https://doi.org/10.1007/PL00009182
T. Biedl, “Triangulating Planar Graphs While Keeping the Pathwidth Small,” in E. Mayr (Ed.), Graph-Theoretic Concepts in Computer Science. WG 2015. Lecture Notes in Computer Science, vol. 9224, Springer, Berlin, Heidelberg, 2016. https://doi.org/10.1007/978-3-662-53174-7_30
G. Kant and H. L. Bodlaender, “Triangulating planar graphs while minimizing the maximum degree,” in O. Nurmi and E. Ukkonen (Eds.), Algorithm Theory — SWAT’92. SWAT 1992. Lecture Notes in Computer Science, vol. 621, Springer, Berlin, Heidelberg, 1992. https://doi.org/10.1007/3-540-55706-7_22
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, “Chapter 23: Minimum Spanning Trees,” in Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001, pp. 561 — 579.
R. L. Graham and P. Hell, “On the history of the minimum spanning tree problem,” Annals of the History of Computing, vol. 7, iss. 1, pp. 43 — 57, 1985.
https://doi.org/10.1109/MAHC.1985.10011
P. Angelini, T. Bruckdorfer, M. Chiesa, F. Frati, M. Kaufmann, and C. Squarcella, “On the area requirements of Euclidean minimum spanning trees,” Computational Geometry: Theory and Applications, vol. 47, iss. 2, part B, pp. 200 — 213, 2014. https://doi.org/10.1016/j.comgeo.2012.10.011
R. Ravi, R. Sundaram, M. Marathe, D. Rosenkrantz, and S. Ravi, “Spanning trees short or small,” SIAM Journal on Discrete Mathematics, vol. 9, iss. 2, pp. 178 — 200, 1996. https://doi.org/10.1137/S0895480194266331
M. Chlebík and J. Chlebíková, “The Steiner tree problem on graphs: Inapproximability results,” Theoretical Computer Science, vol. 406, iss. 3, pp. 207 — 214, 2008.
https://doi.org/10.1016/j.tcs.2008.06.046
R. Jothi, S. K. Mohanty, and A. Ojha, “Fast approximate minimum spanning tree based clustering algorithm,” Neurocomputing, vol. 272, pp. 542 — 557, 2018. https://doi.org/10.1016/j.neucom.2017.07.038
V. V. Romanuke, “Multiple state problem reduction and decision making criteria hybridization,” Research Bulletin of NTUU “Kyiv Polytechnic Institute”, no. 2, pp. 51 — 59, 2016. https://doi.org/10.20535/1810-0546.2016.2.61603
J. M. Boyer and W. J. Myrvold, “On the cutting edge: Simplified planarity by edge addition,” Journal of Graph Algorithms and Applications, vol. 8, iss. 3, pp. 241 — 273, 2005. https://doi.org/10.7155/jgaa.00091
V. V. Romanuke, “A couple of collective utility and minimum payoff parity loss rules for refining Nash equilibria in bimatrix games with asymmetric payoffs,” Visnyk of Kremenchuk National University of Mykhaylo Ostrogradskyy, iss. 1 (108), pp. 38 — 43, 2018. https://doi.org/10.30929/1995-0519.2018.1.38-43
A. K. Sahu, C. Mandal, and S. Agarwal, “Approximate Minimum Spanning Tree for Points Moving in a Euclidean Two-Dimensions Plane,” in N. Chaki, N. Meghanathan, and D. Nagamalai (Eds.), Computer Networks & Communications (NetCom). Lecture Notes in Electrical Engineering, vol. 131, Springer, New York, NY, 2013. https://doi.org/10.1007/978-1-4614-6154-8_67
