×

A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees. (English) Zbl 0414.68035


MSC:

68R10 Graph theory (including graph drawing) in computer science
68W99 Algorithms in computer science
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] , and , ”Enhancements of Spanning Tree Labeling Procedures for Network Optimization,” Research Report CCS 262, Center for Cybernetic Studies, University of Texas at Austin, 1976. To appear in INFOR.
[2] Bradley, Management Science 1 pp 1– (1977)
[3] , , , and ”Past, Present, and Future of Development, Computational Efficiency, and Practical Use of Large-Scale Transportation and Transshipment Computer Codes”, Computers and O.R., 2 (1975), 71–81.
[4] Linear Programming and Extensions, Princeton University Press, Princeton, N.J., 1963. · Zbl 0108.33103
[5] Dennis, JACM 8 pp 132– (1958)
[6] Dial, Communications of the ACM 12 pp 632– (1965)
[7] Dijkstra, Numrical Mathematics 1 pp 269– (1959)
[8] Dreyfus, Operations Research 17 pp 395– (1969)
[9] and , ”A Performance Comparison of Labeling Algorithms for Calculating Shortest Path Trees”, NBS Technical Note 772, U.S. Department of Commerce, 1973.
[10] Glover, Networks 4 pp 191– (1974)
[11] Glover, Management Science 20 pp 793– (1974)
[12] Glover, INFOR 12 pp 293– (1974)
[13] ”Shortest Path Algorithms: A Comparison”, Research Report OR 044–75, Massachusetts Institute of Technology, 1975.
[14] , and , ”Primal Simplex Network Codes: State-of-the-Art Implementation Technology”, Technical Report IEOR 76014, Department of Industrial Engineering and Operations Research, Southern Methodist University, Dallas, Texas, 1976.
[15] Hu, SIAN Journal of Applied Mathematics 15 pp 207– (1967)
[16] ”On Shortest Paths and Sorting”, Proceedings of the ACM 25th Annual Conference, (1972), 510–517.
[17] Karney, Operations Research 24 pp 1056– (1976)
[18] The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addison-Wesley, Reading, Mass., 1973.
[19] The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, Mass., 1973.
[20] ”The Shortest Path Through a Maze”, Proceedings of the International Symposium on the Theory of Switching, 1957.
[21] ”Column Weighting Factors and Other Enhancements to the Augmented Threaded Index Method for Network Optimization”, Joint ORSA/TIMS Conference, San Juan, Puerto Rico, (1974).
[22] Pape, Mathematical Programming 7 pp 212– (1974)
[23] ”Analysis of a Shortest Path Algorithm for Transportation Applications”, Control Analysis Corporation, Technical Report, March 1976.
[24] Srinivasan, JACM 19 pp 712– (1972)
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.