How to find Steiner minimal trees in euclideand-space
Tóm tắt
Từ khóa
Tài liệu tham khảo
A. V. Aho, M. R. Garey, and F. K. Hwang: Rectilinear Steiner trees: Efficient special case algorithms,Networks,7 (1977), 37–58.
M. Ajtai, V. Chvatal, M. M. Newborn, and E. Szemeredi: Crossing free subgraphs,Ann. Discrete Math.,12 (1982), 9–12.
S. K. Chang: The generation of minimal trees with a Steiner topology,J. Assoc. Comput. Math.,19 (1972), 699–711.
F. R. K. Chung and E. N. Gilbert: Steiner trees for the regular simplex,Bull. Inst. Math. Acad. Sinica,4 (1976), 313–325.
F. R. K. Chung and R. L. Graham: A new bound for Euclidean Steiner trees,Ann. N. Y. Acad. Sci,440 (1985), 328–346.
E. J. Cockayne and D. E. Hewgill: Exact computation of Steiner minimal trees in the plane,Inform. Process. Lett.,22 (1986), 151–156.
U. Derigs: A shortest augmenting path method for solving minimum perfect matching problems,Networks,11 (1981), 379–390.
D. Z. Du: On Steiner ratio conjectures, manuscript, Inst. Appl. Math. Academia Sinica, Beijing, China, 1989.
D. Z. Du: The Steiner ratio conjecture is true for six points, to be published.
D. Z. Du, F. K. Hwang, and J. F. Weng: Steiner minimal trees for regular polygons,Discrete Comput. Geom.,2, 1 (1987), 65–87.
H. Edelsbrunner:Algorithms in Combinatorial Geometry, EATCS Monographs in Theoretical Computer Science, Springer-Verlag, Berlin, 1987.
J. H. Friedman, J. L. Bentley, and R. A. Finkel: An algorithm for performing best matches in logarithmic expected time,ACMTOMS,3, 3 (1977), 209–226.
M. R. Garey and D. S. Johnson: The complexity of computing Steiner minimum trees,SIAM J. Algebraic Discrete Methods,32 (1977), 835–859.
M. R. Garey and D. S. Johnson: The rectilinear Steiner minimum tree problem is NP-completeSIAM J. Algebraic Discrete Methods,32 (1977), 826–834.
E. Gekeler: On the solution of systems of equations by the epsilon algorithm of Wynn,Math. Comp.,26, 118 (1972), 427–436.
G. Georgakopoulos and C. H. Papadimitriou: The 1-Steiner tree problem,J. Algorithms, 8 (1987), 122–130.
R. L. Graham and F. K. Hwang: Remarks on Steiner minimal trees I,Bull. Inst. Math. Acad. Sinica,4 (1976), 177–182.
K. Heibig-Hansen and J. Krarup: Improvements of the Held-Karp algorithm for the symmetric TSP,Math. Programming,7 (1974), 87–96.
M. Held and R. M. Karp: The traveling salesman problem and minimum spanning trees,Oper. Res.,18 (1970), 1138–1162.
M. Held and R. M. Karp: The traveling salesman problem and minimum spanning trees, part II,Math. Programming,1 (1971), 6–25.
J. E. Hopcroft and R. E. Tarjan: Efficient planarity testing,J. Assoc. Comput. Math.,21 (1974), 549–558.
F. K. Hwang and D. S. Richards: Steiner tree problems, Bell Laboratories, Murray Hill, NJ, Technical Memorandum 1989. To be published inNetworks.
F. K. Hwang, G. D. Song, G. Y. Ting, and D. Z. Du: A decomposition theorem on Euclidean Steiner minimal trees,Discrete Comput. Geom.,3, 4 (1988), 367–392.
F. K. Hwang and J. F. Weng: Hexagonal coordinate systems and Steiner minimal trees,Discrete Math.,62 (1986), 49–57.
F. K. Hwang and J. F. Weng: The shortest network with a given topology, Bell Laboratories, Murray Hill, NJ, Technical Memorandum 1988.
A. N. C. Kang and D. A. Ault: Some properties of the centroid of a free tree,Inform. Process. Lett,4, 1 (1975), 18–20.
B. Kernighan and D. Ritchie:The C Programming Language, Prentice-Hall, Englewood Cliffs, NJ, 1978.
J. R. Kruskal Jr.: On the shortest spanning subtree of a graph and the traveling salesman problem,Proc. Amer. Math. Soc.,7, 1 (1956), 48–50.
H. W. Kuhn; On a pair of dual nonlinear programs, in:Methods of Nonlinear Programming, pp. 38–54, Ed. J. Abadie, North-Holland, Amsterdam, 1967.
E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Schmoys (eds.)The TST, A Guided Tour of Combinatoral Optimization, Wiley-Interscience, New York, 1985.
G. L. Miller: Finding small simple cycle separators for 2-connected planar graphs,J. Comput. System Sci.,32 (1986), 265–179.
C. Monma, M. Paterson, S. Suri, and F. Yao: Computing Euclidean maximum spanning trees, ACM Computational Geometry Conference 1988, pp. 241–251.
F. P. Preparata and M. I. Shamos:Computational Geometry: An Introduction, Springer-Verlag, New York, 1985.
R. C. Prim: Shortest Connection Networks and Some Generalizations,Bell System Tech. J.,36 (1957), 1389–1401.
P. W. Shor and W. D. Smith: Steiner hulls and θ-hulls, manuscript, 1989.
W. D. Smith: Studies in Discrete and Computational Geometry, Ph.D. Thesis, Program in Applied and Computational Mathematics, Princeton University, September 1988.
D. Smith: Finding the optimum traveling salesman tour forN sites in the Euclidean plane in subexponential time and polynomial space,SIAM J. Comput., submitted.
J. M. Smith, D. T. Lee, and J. S. Liebman: A O(N 1gN) algorithm for Steiner minimal tree problems in the Euclidean metric,Networks,11 (1981), 23–29.
J. Soukup: Minimum Steiner trees, roots of a polynomial, and other magic,ACM SIGMAP Newsletter,22 (1977), 37–51.
R. P. Stanley: The number of faces of simplicial poly topes and spheres, in: Discrete Geometry and Convexity,Proc. N. Y. Acad. Sci., (1986).
R. E. Tarjan: Data structures and network algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, Society of Industrial and Applied Mathematics, Philadelphia, PA, 1983.
J. V. Uspensky:Theory of Equations, McGraw-Hill, New York, 1948.
B. L. van der Waerden:Algebra, Ungar, New York, 1970.
H. E. Warren: Lower Bounds for approximation by nonlinear manifolds,Trans. Amer. Math. Soc., 133 (1968), 167–178.