Building Minimum Spanning Trees under Maximum Edge Length Constraint
Abstract
Given an initial set of planar nodes, the problem is to build a minimum spanning tree connecting the maximum possible number of nodes by not exceeding the maximum edge length. 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 used as graph weights. The edges whose length exceeds the maximum edge length are removed. A minimum spanning tree is built over every disconnected graph. The minimum spanning trees covering a maximum of nodes are selected, among which the tree whose length is minimal is the solution. It is 1.17 % shorter on average for 10 to 80 nodes compared to a nonselected tree.
Keywords: |
Delaunay triangulation; maximum edge length constraint; minimum spanning tree; root node
|
Full Text: |
References
R. L. Graham and P. Hell, “On the history of the minimum spanning tree problem,” Annals of the History of Computing, vol. 7, no. 1, pp. 43–57, Jan.–Mar. 1985. https://doi.org/10.1109/MAHC.1985.10011
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, Mar. 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, May 2023, Art. no. 108829. https://doi.org/10.1016/j.ijepes.2022.108829
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, “Chapter 23: Minimum Spanning Trees,” in Introduction to Algorithms, 2nd ed. MIT Press and McGraw-Hill, 2001, pp. 561–579.
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.
H. Loberman and A. Weinberger, “Formal procedures for connecting terminals with a minimum total wire length,” Journal of the ACM, vol. 4, no. 4, pp. 428 – 437, Oct. 1957. https://doi.org/10.1145/320893.320896
J. C. Gower and G. J. S. Ross, “Minimum spanning trees and single linkage cluster analysis,” Applied Statistics, vol. 18, no. 1, pp. 54 – 61, 1969. https://doi.org/10.2307/2346439
W. B. March, P. Ram, and A. G. Gray, “Fast Euclidean minimum spanning tree: algorithm, analysis, and applications,” in Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, July 25 – 28, 2010, pp. 603–612. https://doi.org/10.1145/1835804.1835882
D. Eppstein, “Spanning trees and spanners,” in J.-R. Sack and J. Urrutia (eds.), Handbook of Computational Geometry. Elsevier, 1999, pp. 425–461. https://doi.org/10.1016/B978-044482537-7/50010-3
G. Robins and J. S. Salowe, “Low-degree minimum spanning trees,” Discrete & Computational Geometry, vol. 14, no. 2, pp. 151–165, 1995. https://doi.org/10.1007/BF02570700
H. Li, W. Mao, A. Zhang, and C. Li, “An improved distribution network reconfiguration method based on minimum spanning tree algorithm and heuristic rules,” International Journal of Electrical Power & Energy, Systems, vol. 82, pp. 466–473, Nov. 2016. https://doi.org/10.1016/j.ijepes.2016.04.017
X. Q. Liao, T. Su, and L. Ma, “Application of neutrosophic minimum spanning tree in electrical power distribution network,” CAAI Transactions on Intelligence Technology, vol. 5, no. 2, pp. 99–105, Apr. 2020. https://doi.org/10.1049/trit.2019.0100
A. Capone, D. Corti, L. Gianoli, and B. Sansó, “An optimization framework for the energy management of carrier ethernet networks with Multiple Spanning Trees,” Computer Networks, vol. 56, no. 17, pp. 3666–3681, Nov. 2012. https://doi.org/10.1016/j.comnet.2012.08.002
B. Fortz, L. Gouveia, and M. Joyce-Moniz, “Optimal design of switched Ethernet networks implementing the Multiple Spanning Tree Protocol,” Discrete Applied Mathematics, vol. 234, pp. 114–130, Jan. 2018. https://doi.org/10.1016/j.dam.2016.07.015
M. M. Devi and M. Geethanjali, “Hybrid of genetic algorithm and minimum spanning tree method for optimal PMU placements,” Measurement, vol. 154, Mar. 2020, Art. no. 107476. https://doi.org/10.1016/j.measurement.2020.107476
P.-J. Wan, G. Călinescu, X.-Y. Li, and O. Frieder, “Minimum-energy broadcasting in static ad hoc wireless networks,” Wireless Networks, vol. 8, no. 6, pp. 607–617, Nov. 2002. https://doi.org/10.1023/a:1020381720601
A. E. F. Clementi, G. Huiban, G. Rossi, Y. C. Verhoeven, and P. Penna, “On the approximation ratio of the MST-based heuristic for the energy-efficient broadcast problem in static ad-hoc radio networks,” in Proceedings of 17th International Parallel and Distributed Processing Symposium (IPDPS 2003), Nice, France, April 22–26, 2003, p. 222. https://doi.org/10.1109/IPDPS.2003.1213407
M. Hajiaghaei-Keshteli, S. Molla-Alizadeh-Zavardehi, and R. Tavakkoli-Moghaddam, “Addressing a nonlinear fixed-charge transportation problem using a spanning tree-based genetic algorithm,” Computers & Industrial Engineering, vol. 59, no. 2, pp. 259–271, Sep. 2010. https://doi.org/10.1016/j.cie.2010.04.007
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, no. 1–3, pp. 3–36, Apr. 2001. https://doi.org/10.1016/S0012-365X(00)00224-7
R. C. Prim, “Shortest connection networks and some generalizations,” Bell System Technical Journal, vol. 36, no. 6, pp. 1389–1401, Nov. 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, no. 1, pp. 269–271, Dec. 1959. https://doi.org/10.1007/BF01386390
J. B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem,” Proceedings of the American Mathematical Society, vol. 7, no. 1, pp. 48–50, 1956. https://doi.org/10.1090/S0002-9939-1956-0078686-7
J. Kleinberg and É. Tardos, Algorithm Design. Boston, Pearson, Addison-Wesley, 2006.
R. Jothi and B. Raghavachari, “Approximation algorithms for the capacitated minimum spanning tree problem and its variants in network design,” ACM Transactions on Algorithms, vol. 1, no. 2, pp. 265–282, Oct. 2005. https://doi.org/10.1145/1103963.1103967
S. Pettie and V. Ramachandran, “An optimal minimum spanning tree algorithm,” Journal of the Association for Computing Machinery, vol. 49, no. 1, pp. 16–34, Jan. 2002. https://doi.org/10.1145/505241.505243
D. A. Bader and G. Cong, “Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs,” Journal of Parallel and Distributed Computing, vol. 66, no. 11, pp. 1366–1378, Nov. 2006. https://doi.org/10.1016/j.jpdc.2006.06.001
D. Lin, Z. Lin, L. Kong, and Y. L. Guan, CMSTR: “A constrained minimum spanning tree based routing protocol for wireless sensor networks,” Ad Hoc Networks, vol. 146, Jul. 2023, Art. no. 103160. https://doi.org/10.1016/j.adhoc.2023.103160
R. E. Edwards, Functional Analysis: Theory and Applications. Holt, Rinehart and Winston, 1965.
V. V. Romanuke, “Optimization of a dataset for a machine learning task by clustering and selecting closest-to-the-centroid objects,” Herald of Khmelnytskyi National University. Technical Sciences, no. 6, vol. 1, pp. 263–265, 2018.
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, no. 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. https://doi.org/10.1007/978-3-642-12971-1
G. Xia, “The stretch factor of the Delaunay triangulation is less than 1.998,” SIAM Journal on Computing, vol. 42, no. 4, pp. 1620–1659, 2013. https://doi.org/10.1137/110832458
F. Hurtado, M. Noy, and J. Urrutia, “Flipping edges in triangulations,” Discrete & Computational Geometry, vol. 22, no. 3, pp. 333–346, Oct. 1999. https://doi.org/10.1007/PL00009464
C. Du, “An algorithm for automatic Delaunay triangulation of arbitrary planar domains,” Advances in Engineering Software, vol. 27, no. 1–2, pp. 21–26, Oct.–Nov. 1996. https://doi.org/10.1016/0965-9978(96)00004-X
L. J. Guibas, D. E. Knuth, and M. Sharir, “Randomized incremental construction of Delaunay and Voronoi diagrams,” Algorithmica, vol. 7, no. 1–6, pp. 381–413, Jun. 1992. https://doi.org/10.1007/BF01758770
V. V. Romanuke, “Speedup of the k-means algorithm for partitioning large datasets of flat points by a preliminary partition and selecting initial centroids,” Applied Computer Systems, vol. 28, no. 1, pp. 1–12, Aug. 2023. https://doi.org/10.2478/acss-2023-0001
V. V. Romanuke, “Accurate detection of multiple targets by uniform rectangular array radar with threshold soft update and area rescanning,” Information and Telecommunication Sciences, vol. 13, no. 2, pp. 62–71, Dec. 2022. https://doi.org/10.20535/2411-2976.22022.62-71
S. Li, “A 1.488 approximation algorithm for the uncapacitated facility location problem,” in Automata, Languages and Programming. Lecture Notes in Computer Science, L. Aceto, M. Henzinger, and J. Sgall, Eds. vol. 6756. Springer, 2011, pp. 77–88. https://doi.org/10.1007/978-3-642-22012-8_5
N. Megiddo and A. Tamir, “On the complexity of locating linear facilities in the plane,” Operations Research Letters, vol. 1, no. 5, pp. 194–197, Nov. 1982. https://doi.org/10.1016/0167-6377(82)90039-6
R. Zhou, L. Shu, and Y. Su, “An adaptive minimum spanning tree test for detecting irregularly-shaped spatial clusters,” Computational Statistics & Data Analysis, vol. 89, pp. 134–146, Sep. 2015. https://doi.org/10.1016/j.csda.2015.03.008
Y. Li, T. Chu, Y. Liu, H. Zhang, F. Dong, Q. Gai, Y. Shi, H. Ma, F. Zhao, K. Che, N. Mao, and H. Xie, “Classification of major depression disorder via using minimum spanning tree of individual high-order morphological brain network,” Journal of Affective Disorders, vol. 323, pp. 10–20, Feb. 2023. https://doi.org/10.1016/j.jad.2022.11.029
DOI: 10.7250/itms-2023-0003
Refbacks
- There are currently no refbacks.
Copyright (c) 2023 Vadim Romanuke
This work is licensed under a Creative Commons Attribution 4.0 International License.