On minimum stars, minimum Steiner stars, and maximum matchings

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On minimum stars, minimum Steiner stars, and maximum matchings

Full text

Pdf (1.07 MB)

Source

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

Miami Beach, Florida, United States

Pages: 217 - 226

Year of Publication: 1999

ISBN:1-58113-068-6

Authors

Sándor P. Fekete	Center for Parallel Computing, Universität zu Köln, 50923 Köln, Germany
Henk Meijer	Department of Computer Science, Queen's University, Kingston, Ont K7L 3N6, Canada

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): 8, Citation Count: 0

Additional Information:

references 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/304893.304974 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	Chanderjit Bajaj, The algebraic degree of geometric optimization problems, Discrete & Computational Geometry, v.3 n.2, p.177-191, Jan, 1988 [doi>10.1007/BF02187906]
	2	Alexander I. Barvinok , David S. Johnson , Gerhard J. Woeginger , Russell Woodroofe, The Maximum Traveling Salesman Problem Under Polyhedral Norms, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.195-201, June 22-24, 1998
	3	Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983 [doi>10.1145/800061.808735]
	4	Manuel Blum , Robert W. Floyd , Vaughan Pratt , Ronald L. Rivest , Robert E. Tarjan, Linear time bounds for median computations, Proceedings of the fourth annual ACM symposium on Theory of computing, p.119-124, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804904]
	5	D.-Z. Du and F. K. Hwang. A proof of the Gilbert- Pollak conjecture on the Steiner ratio. Algorithmica, 7 (1992), 121-135.
	6	J. Edmonds. Maximum matching and a polyhedron with 0, 1-vertices. Journal o/ Research of the National Bureau of Standards (B), 69 (1965), 69-87.
	7	Sándor P. Fekete, Simplicity and hardness of the maximum traveling salesman problem under geometric distances, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.337-345, January 17-19, 1999, Baltimore, Maryland, United States
	8	J. Andrew Fingerhut , Subhash Suri , Jonathan S. Turner, Designing least-cost nonblocking broadband networks, Journal of Algorithms, v.24 n.2, p.287-309, Aug. 1997 [doi>10.1006/jagm.1997.0866]
	9	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	10	A. J. Goldmann. Optimal center location in simple networks. Transportation Science, 5 (1971), 212-221.
	11	F. K. Hwang, D. S. Richards, and P. Winter. The Steiner Tree Problem. Elsevier Science, Amsterdam 1992.
	12	O. Kariv and L. S. Haldmi. An algorithmic approach to network location problems, ii: The p-medians. SlAM Journal on Applied Mathematics, 37 (1979), 539-560.
	13	M. Spivak. Calculus. W.A. Benjamin, Menlo Park, California, 1967.
	14	S. Suri. Problem # 5. Problem session of the 14th A CM Symposium on Computational Geometry, 1998. http://www, cs .duke. edu/-pankaj/scg98-openprobs /open-probs. html.
	15	Arie Tamir , Joseph S. B. Mitchell, A maximum b-matching problem arising from median location models with applications to the roommates problem, Mathematical Programming: Series A and B, v.80 n.2, p.171-194, Jan. 16, 1998 [doi>10.1007/BF01581725]