The complexity of the capacitated tree problem
Tóm tắt
Từ khóa
Tài liệu tham khảo
Aho A. V., 1974, The Design and Analysis of Computer Algorithms
Bellmore M., 1968, The Traveling Salesman Problem: A Survey, J. ORSA, 16, 538
Christofides N. “Worst Case Analysis of an Algorithm for the Traveling Salesman Problem ” presented in the Carnegie‐MellonSymposium on Algorithms and Complexity: New Trends and Ideas Pittsburgh April1976.
Garey M. R. R. L.GrahamandD. S.Johnson “Some NP‐Complete Geometric Problems ”Proc. 8th SIGACT Symp. on the Theory of Computing 1976 pp.10–22.
Garey M. R.andD. S.Johnson “Strong NP‐Completeness Results: Motivation Examples and Implications ” Bell Laboratories TR Abstract in theProc of the ORSA‐TIMS Meeting Miami 1976.
Gillmore E. N., 1965, Random Minimal Trees, J. SIAM, 13, 376
Johnson D. S.andS.Lin private communication Bell Laboratories September1976.
Karp R. M., 1976, The Probabilistic Analysis of Some Combinatorial Search Algorithms
Kershenbaum A.andR. R.Boorstyn “Centralized Tele‐processing Network Design ” Manuscript Network Analysis Corporation 1976.
Kruskal J. B., 1956, On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proc. Amer. Math. Soc., 7
Papadimitriou C. H., 1975, The Euclidean Traveling Salesman Problem is NP‐Complete
Papadimitriou C. H. “The Complexity of Combinatorial Optimization Problems ” Ph. D. Thesis Princeton University 1976.
Shamos M. I.andD.Hoey “Closest‐Point Problems ”Proc. 6th Ann. Symp. on Found. Comp. Sci. 1975 pp.151–162.
Sharma R. L.andM. T.El Bardai “Suboptimal Communications Network Synthesis ”Proc. Internat. Conf. on Communications 1970 pp.19.11–19.16.
Steiglitz K. P.WeinerandD. J.Kleitman “The Design of Optimum Cost Survivable Networks ”IEEE Trans. on Circuit Theory CT‐16 1969 pp.455–460.
Whitney V. K. M. “Comparison of Network Topology Optimization Algorithms ”Proc. Internat. Conf. on Computer Communication 1972 pp.332–337.