Construction of multidimensional spanner graphs, with applications to minimum spanning trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Construction of multidimensional spanner graphs, with applications to minimum spanning trees

Full text

Pdf (432 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: 256 - 261

Year of Publication: 1991

ISBN:0-89791-426-0

Author

Jeffrey S. Salowe

Department of Computer Science, University of Virginia, Charlottesville, Virginia

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): 2, Downloads (12 Months): 14, Citation Count: 6

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.109677 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	Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Proceedings of the sixth annual symposium on Computational geometry, p.203-210, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98567]
	2	I. Althöfer , G. Das , D. Dobkin , D. Joseph, Generating sparse spanners for weighted graphs, Proceedings of the second Scandinavian workshop on Algorithm theory, p.26-37, July 1990, Bergen, Sweden
	3	P Chew, There is a planar graph almost as good as the complete graph, Proceedings of the second annual symposium on Computational geometry, p.169-177, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10534]
	4	Kenneth L. Clarkson, Fast expected-time and approximation algorithms for geometric minimum spanning trees, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.342-348, December 1984 [doi>10.1145/800057.808699]
	5	G. Das , D. Joseph, Which triangulations approximate the complete graph?, Proceedings of the international symposium on Optimal algorithms, p.168-192, November 1989, Varna, Bulgaria
	6	David P. Dobkin , Steven J. Friedman , Kenneth J. Supowit, Delaunay graphs are almost as good as complete graphs, Discrete & Computational Geometry, v.5 n.4, p.399-407, Jul. 1990 [doi>10.1007/BF02187801]
	7	Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
	8	H N Gabow , Z Galil , T Spencer , R E Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, v.6 n.2, p.109-122, 1986 [doi>10.1007/BF02579168]
	9	J. M. Keil, Approximating the complete Euclidean graph, No. 318 on SWAT 88: 1st Scandinavian workshop on algorithm theory, p.208-213, January 1988, Halmstad, Sweden
	10	J. Mark Keil , Carl A. Gutwin, The Delauney Triangulation Closely Approximates the Complete Euclidean Graph, Proceedings of the Workshop on Algorithms and Data Structures, p.47-56, August 17-19, 1989
	11	C. Levcopoulos , A. Lingas, There are planar graphs almost as good as the complete graphs and as short as minimum spanning trees (invited), Proceedings of the international symposium on Optimal algorithms, p.9-13, November 1989, Varna, Bulgaria
	12	M.I. Shamos and D. Hoey, Closest-Point Problems, Sixteenth IEEE Symposium Found. Comput. Sci., 1975, pp. 151-162.
	13	Pravin M. Vaidya, Minimum spanning trees in k-dimensional space, SIAM Journal on Computing, v.17 n.3, p.572-582, June 1988 [doi>10.1137/0217035]
	14	P. M. Vaidya, An O(n log n) algorithm for the all-nearest-neighbors problem, Discrete & Computational Geometry, v.4 n.2, p.101-115, Jan. 1989 [doi>10.1007/BF02187718]
	15	A.C. Yao, On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems, Siam J. on Computing, 11, 1982, pp. 721- 736.

CITED BY 6

	Gautam Das , Giri Narasimhan, A fast algorithm for constructing sparse Euclidean spanners, Proceedings of the tenth annual symposium on Computational geometry, p.132-139, June 06-08, 1994, Stony Brook, New York, United States
	Paul B. Callahan , S. Rao Kosaraju, Faster algorithms for some geometric graph problems in higher dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.291-300, January 25-27, 1993, Austin, Texas, United States
	Timothy M. Chan, Approximate nearest neighbor queries revisited, Proceedings of the thirteenth annual symposium on Computational geometry, p.352-358, June 04-06, 1997, Nice, France
	Paul B. Callahan , S. Rao Kosaraju, Algorithms for dynamic closest pair and n-body potential fields, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.263-272, January 22-24, 1995, San Francisco, California, United States
	Barun Chandra , Gautam Das , Giri Narasimhan , José Soares, New sparseness results on graph spanners, Proceedings of the eighth annual symposium on Computational geometry, p.192-201, June 10-12, 1992, Berlin, Germany
	Surender Baswana , Sandeep Sen, A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs, Random Structures & Algorithms, v.30 n.4, p.532-563, July 2007