Two probabilistic results on rectilinear Steiner trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Two probabilistic results on rectilinear Steiner trees

Full text

Pdf (671 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 433 - 441

Year of Publication: 1986

ISBN:0-89791-193-8

Author

M W Bern

Computer Science Division, University of California, Berkeley, California

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 19, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/12130.12175 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AGH	A. V. Aho, M. R. Garey, and F. K. Hwang, "Rectilinear Steiner Trees: Efficient Special Case Algorithms," Networks 7, 1977, pp. 37-58.
	BdC	M. W. Bern and M. de CarvaIho, "Thompson's Heuristic for the Rectilinear Steiner Tree Problem," unpublished manuscript, U. of California at Berkeley, 1985.
	CG	F. R. K. Chung and R. L. Graham, "On Steiner Trees for Bounded Point Sets," Geom. Dedicata 11, 1981, pp. 363-361.
	CH	F. R. K. Chung and F. K. Hwang, "The Largest Minimal Rectilinear Steiner Trees for a Set of n Points Enclosed in a Rectangle with Given Perimeter," Networks 9, 1979, pp. 19-36.
	GJ	M. R. Garey and D. S. Johnson, "The Rectilinear Steiner Tree Problem is NP-Complete," SIAM J. of Appl. Math., 32, 1977, pp. 826-834.
	GR	I. S. Gradshteyn and I. M. Ryzhik, Tables of Integrals, Series, and Products, Academic Press, 1980, p. 337.
	Ha	M. Hanan, "On Steiner's Problem with Rectilinear Distance," SIAM J. of Appl. Math., 14, 1966, pp. 255- 265.
	H76	F. K. Hwang, "On Steiner Minimal Trees with Rectilinear Distance," SIAM J. of Appl. Math., 30, 1976, pp. 104-114.
	H78	F. K. Hwang, "The Rectilinear Steiner Problem," Design Automation and Fault-Tolerant Computing 2, 1978, pp. 303-310.
	H79	F. K. Hwang, "An O(NlogN) Algorithm for Suboptimal Rectilinear Steiner Trees," IEEE Trans. on Circuits and Systems 26, 1979, pp. 75-77.
	HRK	M. Haimovich and A. H. G. Rinnooy Kan, personal communication with A. H. G. Rinnooy Kan.
	KS	R. M. Karp and J. M. Steele, "Probabilistic Analysis of Heuristics", Chapter 6 of The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimizat/on, edited by E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, Wiley, 1985.
	KoSh	J. KomlSs and M. T. Shing, ~Probabilistic Partitioning Algorithms for the Rectilinear Steiner Problem," Networks 15, 1985, pp. 413-424.
	Kr	J. B. Kruskal, "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem,", Proc. AMS 7, 1956, pp. 48-50.
	L	E. L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, 1976, p. 290.
	LBH	J. H. Lee, N. K. Bose, and F. K. Hwang, "Use of Steiner's Problem in Suboptimal Routing in Rectilinear Metric," IEEE Trans. on Circuits and Systems 23, 1976, pp. 470-476.
	ML	J. MacGregor-Smith and J. S. Liebman, "Steiner Trees, Steiner Circuits, and the Interference Problem in Building Design," Engineering Optimization 4, 1979, pp. 15-36.
	MLL	J. MacGregor-Smith, D. T. Lee, and J. S. Liebman, "An O(NlogN) Heuristic Algorithm for the Rectilinear Steiner Problem," Engineering Optimization 4, 1980, pp. 179-192.
	N	A. Ng, U. of California at Berkeley, personal communication.
	P	H. R. Pitt, Tauberian Theorems, Oxford University Press, 1958, pp. 37-42.
	Pr	R. C. Prim, "Shortest Connecting Networks and Some Generalizations," Bell Syst. Tech. J. 36, 1957, pp. 1389-1401.
	Se	M. Servit, "Heuristic Algorithms for Rectilinear Steiner Trees," Digital Processes 7, 1981, pp. 21-32.
	St	J. M. Steele, "Subadditive Euclidean Functionals and Nonlinear Growth in Geometric Probability," Ann. Probability 9, 1982, pp. 365-376.
	Th	C. D. Thompson, U. of California at Berkeley, persenal communication.
	YW	Y. Y. Yang and O. Wing, "Suboptimal Algorithm for a Wire Routing Problem," IEEE Trans. Circuit Theory 19, 1972, pp. 508-511.