BUILDING MINIMUM SPANNING TREES BY LIMITED NUMBER OF NODES OVER TRIANGULATED SET OF INITIAL NODES
DOI:
https://doi.org/10.20535/2411-2976.12023.41-50Keywords:
minimum spanning tree, triangulation, edge lengths, redundant nodes, root nodeAbstract
Background. The common purpose of modelling and using minimum spanning trees is to ensure efficient coverage. In many tasks of designing efficient telecommunication networks, the number of network nodes is usually limited. In terms of rational allocation, there are more possible locations than factually active tools to be settled to those locations.
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 can be less than the cardinality of the initial set. The root node is primarily assigned, but it can be changed if needed.
Methods. To obtain a set of edges, a Delaunay triangulation is performed over the initial set of nodes. Distances between every pair of the nodes in respective edges are calculated. These distances being the lengths of the respective edges are used as graph weights, and a minimum spanning tree is built over this graph.
Results. The problem always has a solution if the desired number of nodes (the number of available recipient nodes) is equal to the number of initially given nodes. If the desired number is lesser, the maximal edge length is found and the edges of the maximal length are excluded while the number of minimum spanning tree nodes is greater than the desired number of nodes.
Conclusions. To build a minimum spanning tree by a limited number of nodes it is suggested to use the Delaunay triangulation and an iterative procedure in order to meet the desired number of nodes. Planar nodes of an initial set are triangulated, whereupon the edge lengths are used as weights of a graph. The iterations to reduce nodes are done only if there are redundant nodes. When failed, the root node must be changed before the desired number of nodes is changed.
References
J. Nešetřil, E. Milková, and H. Nešetřilová, “Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history,” Discrete Mathematics, vol. 233, iss. 1 — 3, pp. 3 — 36, 2001.
https://doi.org/10.1016/S0012-365X(00)00224-7
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
Y. K. Dalal and R. M. Metcalfe, “Reverse path forwarding of broadcast packets,” Communications of the ACM, vol. 21, iss. 12, pp. 1040 — 1048, 1978. https://doi.org/10.1145/359657.359665
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
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
S. Pettie and V. Ramachandran, “An optimal minimum spanning tree algorithm,” Journal of the Association for Computing Machinery, vol. 49, iss. 1, pp. 16 — 34, 2002. https://doi.org/10.1145/505241.505243
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. C. Prim, “Shortest connection networks and some generalizations,” Bell System Technical Journal, vol. 36, iss. 6, pp. 1389 — 1401, 1957.
https://doi.org/10.1002/j.1538-7305.1957.tb01515.x
E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, iss. 1,
pp. 269 — 271, 1959.
https://doi.org/10.1007/BF01386390
T. Cormen, C. E. Leiserson, and R. L. Rivest, and C. Stein, Introduction to Algorithms, Third Edition. MIT Press, 2009.
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
R. E. Tarjan, “Chapter 6. Minimum spanning trees. 6.2. Three classical algorithms,” Data Structures and Network Algorithms, in CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial and Applied Mathematics, 1983, pp. 72 — 77.
S. Chakraborty, A. Mukherjee, V. Raman, and S. Rao Satti, “Frameworks for designing in-place graph algorithms,” Journal of Computer and System Sciences, vol. 123, pp. 1 — 19, 2022.
https://doi.org/10.1016/j.jcss.2021.07.004
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
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
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.
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
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.
