×

An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem. (English) Zbl 0760.90088

Summary: This paper details the design, implementation, and testing of a one edge pass non-greedy algorithm for the minimum spanning tree problem. The use of network labeling procedures, and path weights to screen entering edges, provides a novel implementation of this algorithm. The choice of data structures also allows for an efficient implementation of reoptimization procedures, which have hitherto never been studied. Comprehensive results on the performance of both the greedy and non- greedy algorithms in optimization and reoptimization modes under various screening criteria, graph topologies, sizes and densities, and weight distributions are presented. The empirical results based on 855 problems bear out Tarjan’s conjecture that greedy algorithms have a competitive advantage over non-greedy algorithms for the minimum spanning tree problem, except in special cases. However, for the problems tested, when a small percentage of edge weights are changed, non-greedy approaches are competitive with greedy algorithms in reoptimization mode.

MSC:

90C35 Programming involving graphs or networks
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcraft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA
[2] Barr, R.; Glover, F.; Klingman, D., Enhancements of spanning tree labelling procedures for network optimization, INFOR, 17, 4, 16-33 (1979) · Zbl 0403.90083
[3] Berge, C.; Ghouila-Houri, A., Programming, Games and Transportation Networks (1965), Wiley: Wiley New York
[4] Boruvka, O., O jistem problemu minimalnim, Práca Moravské Přírodovědecké Společnosti v Brne, 3, 37-58 (1926)
[5] Brennan, J. J., Minimal spanning trees and partial sorting, Operations Research Letters, 1, 3, 113-116 (1982) · Zbl 0488.90071
[6] Cheriton, D.; Tarjan, R. E., Finding minimum spanning trees, SIAM Journal on Computing, 5, 4, 724-742 (1976) · Zbl 0358.90069
[7] Choquet, G., Etude de certains reseaux de routes, C. R. Acad. Sci. Paris, 206, 310-313 (1938) · JFM 64.0707.02
[8] Dijkstra, E. W., A note on two problems in connection with graphs, Numerische Mathematik, 1, 269-271 (1959) · Zbl 0092.16002
[9] Edmonds, J., Matroids and the greedy algorithm, Mathematical Programming, 1, 127-271 (1971) · Zbl 0253.90027
[10] Gabow, H. N.; Tarjan, R. E., Efficient algorithms for a family of matroid intersection problems, (Technical Report CU-CS-214-82 (1985), University of Colorado) · Zbl 0545.05029
[11] Gilsinn, J.; Witzgall, C., A performance comparison of labeling algorithms for calculating shortest path trees, (NBS Technical Note 772 (1973), US Department of Commerce)
[12] Glover, F.; Karney, D.; Klingman, D., The augmented predecessor index method for locating steppingstone paths and assigning dual prices in distribution problems, Transportation Science, 6, 2, 171-179 (1972)
[13] Glover, F.; Klingman, D., Finding minimum spanning trees with a fixed number of links at a node, (Prekopa, A., Colloquia Mathematica Societatis (1974), North-Holland: North-Holland New York), 425-439 · Zbl 0395.90077
[14] Glover, F.; Klingman, D.; Phillips, N.; Schneider, R., New polynomial shortest path algorithms and their computational attributes, Management Science, 31, 9, 1106-1128 (1985) · Zbl 0609.90103
[15] Glover, F.; Novick, B., The 2-quasi-greedy algorithm for cardinality constrained matroid bases, Discrete Applied Mathematics, 13, 277-286 (1986) · Zbl 0596.90094
[16] Golden, B. L.; Magnanti, T. L.; Nguyen, H. G., Implementing vehicle routing algorithms, Networks, 7, 113-148 (1977) · Zbl 0359.90054
[17] Gomory, R. E.; Hu, T. C., Multiterminal network flows, SIAM Journal of Applied Mathematics, 9, 551-571 (1961) · Zbl 0112.12405
[18] Gower, J. C.; Ross, G. J.S., Minimum spanning trees and single linkage cluster analysis, Applied Statistics, 18, 54-64 (1969)
[19] Graham, R. L.; Hell, P., On the history of the minimum spanning tree problem, Annals of the History of Computing, 7, 1, 43-58 (1985) · Zbl 0998.68003
[20] Haymond, R. E.; Jarvis, J. P.; Shier, D. R., ALGORITHM 613: Minimum spanning tree for moderate integer weights, ACM Transactions on Mathematical Software, 10, 1, 108-110 (1984) · Zbl 0541.68042
[21] Haymond, R. E.; Jarvis, J. P.; Shier, D. R., Computational methods for minimum spanning tree algorithms, SIAM Journal on Scientific and Statistical Computing, 5, 1, 157-174 (1984) · Zbl 0537.68069
[22] Held, M.; Karp, R. M., The traveling salesman problem and minimum spanning trees, Operations Research, 18, 1138-1162 (1970) · Zbl 0226.90047
[23] Held, M.; Karp, R. M., The traveling salesman problem and minimum spanning trees II, Mathematical Programming, 1, 6-25 (1971) · Zbl 0232.90038
[24] Jarvis, J. P.; Whited, D. E., Computational experience with minimum spanning tree algorithms, Operations Research Letters, 2, 1, 36-41 (1983) · Zbl 0517.90086
[25] Johnson, D. B., Priority queues with update and finding minimum spanning trees, Information Processing Letters, 4, 3, 53-57 (1975) · Zbl 0318.68032
[26] Kershenbaum, A.; Sylke, R. V., Computing minimum spanning trees efficiently, (Proceedings ACM National Conference (1972)), 518-527
[27] Kevin, V.; Whitney, M., Algorithm 422: Minimal spanning tree [H]”, Communications of the ACM, 15, 273-274 (1972)
[28] Kruskal, J. B., On the shortest spanning subtree of a graph and the traveling salesman problem, (Proceedings of the American Mathematical Society, 7 (1956)), 48-50 · Zbl 0070.18404
[29] Loberman, H.; Weinberger, A., Formal procedures for connecting terminals with a minimum total wire length, Journal of ACM, 4, 428-437 (1957)
[30] Pynn, C.; Warren, J. H., Improved algorithm for the construction of minimal spanning trees, Electronics Letters, 8, 143-144 (1972)
[31] Prim, R. C., Shortest connection networks and some generalizations, The Bell System Technical Journal, 36, 6, 1389-1401 (1957)
[32] Spira, P. M.; Pan, A., On finding and updating spanning trees and shortest paths, Siam Journal on Computing, 4, 3, 375-380 (1975) · Zbl 0325.05119
[33] Tarjan, R. E., Data Structures and Network Algorithms, (CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44 (1983), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia) · Zbl 0749.90027
[34] Van Slyke, R.; Frank, H., Network reliability analysis Pt. I, Networks, 1, 279-290 (1972) · Zbl 0239.94041
[35] Yao, A. C., An \(O(e\) log \(v)\) algorithm for finding minimum spanning trees, Information Processing Letters, 4, 21-23 (1975) · Zbl 0307.68028
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.