Transitions in geometric minimum spanning trees (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Transitions in geometric minimum spanning trees (extended abstract)

Full text

Pdf (951 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the seventh annual symposium on Computational geometry table of contents

North Conway, New Hampshire, United States

Pages: 239 - 249

Year of Publication: 1991

ISBN:0-89791-426-0

Authors

Clyde Monma	Bell Communications Research, 445 South Street, Morristown, NJ
Subhash Suri	Bell Communications Research, 445 South Street, Morristown, NJ

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 15, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/109648.109675 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.

	1	T. Asano , B. Bhattacharya , M. Keil , F. Yao, Clustering algorithms based on minimum and maximum spanning trees, Proceedings of the fourth annual symposium on Computational geometry, p.252-257, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73419]
	2	M. J. Atallah. Some dynamic computational geometry problems. Journal of Computational and Applied Mathematics, Vol. 11, 1985, pp. 1117-1181.
	3	B Chazelle , R Cole , P Preparata , C Yap, New upper bounds for neighbor searching, Information and Control, v.68 n.1-3, p.105-124, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80030-4]
	4	L. Paul Chew , Robert L. (Scot) Dyrsdale, III, Voronoi diagrams based on convex distance functions, Proceedings of the first annual symposium on Computational geometry, p.235-244, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323264]
	5	William H. Cunningham, Optimal attack and reinforcement of a network, Journal of the ACM (JACM), v.32 n.3, p.549-561, July 1985 [doi>10.1145/3828.3829]
	6	M E Dyer, On a multidimensional search technique and its application to the Euclidean one centre problem, SIAM Journal on Computing, v.15 n.3, p.725-738, August 1986 [doi>10.1137/0215052]
	7	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	8	G. Gallo , M. D. Grigoriadis , R. E. Tarjan, A fast parametric maximum flow algorithm and applications, SIAM Journal on Computing, v.18 n.1, p.30-55, Feb. 1989 [doi>10.1137/0218003]
	9	D. Gusfield. Bounds for the parametric spanning tree problem. Proc. Humbolt Conf on Graph Theory, Combinatorics and Computing. Utilitas Mathematica, 1979, pp. 173-183.
	10	Daniel Mier Gusfield, Sensitivity analysis for combinatorial optimization, 1980
	11	Dan Gusfield, Parametric Combinatorial Computing and a Problem of Program Module Distribution, Journal of the ACM (JACM), v.30 n.3, p.551-563, July 1983 [doi>10.1145/2402.322391]
	12	Dan Gusfield , Robert W. Irving, Parametric stable marriage and minimum cuts, Information Processing Letters, v.30 n.5, p.255-259, March 1989 [doi>10.1016/0020-0190(89)90204-4]
	13	D. Gusfield and C. Martel. A fast algorithm for the generalized parametric minimum cut problem and applications. UC Davis, Technical Report CSE-89- 21, 1989.
	14	C. Monma and S. Suri. Transitions in geometric minimum spanning trees. Technical Memorandum, Bell Communications Research, 1991.
	15	J. C. Picard and M. Queyranne. Selected applications of minimum cuts in a network. INFOR- Canadian J, of Oper. ivies. Inf. Proc. 20, 1982, pp. 394-422.
	16	J. C. Picard and It. Ratliff. A cut approach to the rectilinear distanc9 facility location problem. Operations Research, 1978, pp. 422-433.
	17	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
	18	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	19	A. C. C. Yao. On constructing minimum spanning trees in k-dimensional space and related problems. SiAM J. of Computing, Vol. 11(4), 1982, pp. 721- 736.
	20	C.T. Zahn. Graph-theoretical methods for detecting gestalt clusters, iEEE Transactions on Computers, C-20, 1971, pp. 68-86.

CITED BY 5

	Hongju Cheng , Qin Liu , Xiaohua Jia, Heuristic algorithms for real-time data aggregation in wireless sensor networks, Proceeding of the 2006 international conference on Communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada
	Peter Eades , Sue Whitesides, The realization problem for Euclidean minimum spanning trees is NP-hard, Proceedings of the tenth annual symposium on Computational geometry, p.49-56, June 06-08, 1994, Stony Brook, New York, United States
	Alan Saalfeld, Sorting Spatial Data for Sampling and Other Geographic Applications, Geoinformatica, v.2 n.1, p.37-57, March 1998
	Ning Li , Jennifer C. Hou, Localized topology control algorithms for heterogeneous wireless networks, IEEE/ACM Transactions on Networking (TON), v.13 n.6, p.1313-1324, December 2005
	Prosenjit Bose, On embedding an outer-planar graph in a point set, Computational Geometry: Theory and Applications, v.23 n.3, p.303-312, November 2002