A matter of degree

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees

Full text

Pdf (808 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-second annual ACM symposium on Theory of computing table of contents

Portland, Oregon, United States

Pages: 537 - 546

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

J. Könemann	Carnegie Mellon University, GSIA, Pittsburgh, PA
R. Ravi	Carnegie Mellon University, GSIA, Pittsburgh, PA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 23, Citation Count: 6

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/335305.335371 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	Fred Bauer , Anujan Varma, DEGREE-CONSTRAINED MULTICASTING IN POINT-TO-POINT NETWORKS, University of California at Santa Cruz, Santa Cruz, CA, 1995
	2	J. Cheriyan and R. Ravi. Approximation algorithms for network problems. Lecture Notes (http://www.gsia.cmu.edu/andrew/ravi), 1998.
	3	S. Chopra. On the spanning tree polyhedron. Operations Research Letters, 8:25-29, 1989.
	4	Stephen Deering , Deborah Estrin , Dino Farinacci , Van Jacobson , Ching-Gung Liu , Liming Wei, An architecture for wide-area multicast routing, Proceedings of the conference on Communications architectures, protocols and applications, p.126-135, August 31-September 02, 1994, London, United Kingdom
	5	T. Fischer. Optimizing the degree of minimum weight spanning trees. Technical Report TR 93-1338, Dept. of Computer Science, Cornell University, Ithaca, NY 14853, 1993.
	6	Sally Floyd , Van Jacobson , Steve McCanne , Ching-Gung Liu , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.342-356, August 28-September 01, 1995, Cambridge, Massachusetts, United States
	7	Martin Fürer , Balaji Raghavachari, Approximating the minimum-degree Steiner tree to within one of optimal, Journal of Algorithms, v.17 n.3, p.409-423, Nov. 1994
	8	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
	9	M. Held and R. M. Karp. The traveling-salesman problem and minimum spanning trees: part II. Math. Programming, 1:6-25, 1971.
	10	Michael Held, Philip Wolfe, and Harlan P. Crowder. Validation of subgradient optimization. Mathematical Programming, 6( 1):62-88, 1974.
	11	Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	12	Samir Khuller , Balaji Raghavachari , Neal Young, Low-Degree Spanning Trees of Small Weight, SIAM Journal on Computing, v.25 n.2, p.355-368, February 1996 [doi>10.1137/S0097539794264585]
	13	Philip Klein , R. Ravi, A nearly best-possible approximation algorithm for node-weighted Steiner trees, Journal of Algorithms, v.19 n.1, p.104-115, July 1995 [doi>10.1006/jagm.1995.1029]
	14	George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
	15	B.T. Polyak. A general method of solving extremum problems. Doklady Akademmi Nauk SSSR, 174(1):33- 36, 1967.
	16	R. Ravi , M. V. Marathe , S. S. Ravi , D. J. Rosenkrantz , H. B. Hunt, III, Many birds with one stone: multi-objective approximation algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.438-447, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167209]
	17	A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
	18	Wen De Zhong , Jaidev Kaniyil , Y. Onozato, A copy network with shared buffers for large-scale multicast ATM switching, IEEE/ACM Transactions on Networking (TON), v.1 n.2, p.157-165, April 1993 [doi>10.1109/90.222923]

CITED BY 6

	Aravind Srinivasan, New approaches to covering and packing problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.567-576, January 07-09, 2001, Washington, D.C., United States
	Timothy M. Chan, Euclidean bounded-degree spanning tree ratios, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Daniel Golovin , Viswanath Nagarajan , Mohit Singh, Approximating the k-multicut problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.621-630, January 22-26, 2006, Miami, Florida
	Jochen Könemann , R. Ravi, Primal-dual meets local search: approximating MST's with nonuniform degree bounds, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Eric Rosenberg, Hierarchical topological network design, IEEE/ACM Transactions on Networking (TON), v.13 n.6, p.1402-1409, December 2005
	Mohammad Ghodsi , Hamid Mahini , Kian Mirjalali , Shayan Oveis Gharan , Amin S. Sayedi R. , Morteza Zadimoghaddam, Spanning trees with minimum weighted degrees, Information Processing Letters, v.104 n.3, p.113-116, October, 2007