The complexity of restricted spanning tree problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The complexity of restricted spanning tree problems

Full text

Pdf (1.36 MB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 2 (April 1982) table of contents

Pages: 285 - 309

Year of Publication: 1982

ISSN:0004-5411

Authors

Christos H. Papadimitriou	National Technical University of Athens, Athens, Greece
Mihalis Yannakakis	Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 77, Citation Count: 9

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/322307.322309 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	EDMONDS, J. Paths, trees, and flowers Canad J Math 17 (1965), 449--467.
	3	EDMONDS, J.Submodular funcuons, matrolds and certain polyhedra, lrt Combinatorial Structures and Thelr Apphcatwns, Proc. of the Calgary fnternauonal Conference, R Guy, Ed., Gordon and Breach, N.Y., 1970, pp. 69-87.
	4	EDMONDS, J Matrolds and the greedy algorithm. Math. Prog 1 (1971), 127-136.
	5	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
	6	Steven L. Tanimoto , Alon Itai , Michael Rodeh, Some Matching Problems for Bipartite Graphs, Journal of the ACM (JACM), v.25 n.4, p.517-525, Oct. 1978 [doi>10.1145/322092.322093]
	7	JOHNSON, D.S., AND LIN, S Private communicat,on, Feb. 1976
	8	KARP, R M. Reductbdlty among combmatonal problems. In Complexlty of Computer Computations, R. E. Mdler and J W. Thatcher, Eds., Plenum, New York, 1972, pp 85-103
	9	KRUSKAL, J B On the shortest spanning subtree of the graph and the traveling salesman problem. Proc Am Math. Soc. 2 (1956), 48-50.
	10	LAWLER, E.L. Matrold intersection algonth_ms Math Prog 9 (1975), 31-56.
	11	LAWLER, E L Combinatorial Optimization Networks and Matroids. Holt-Rhinehart-Wmston, 1977.
	12	LIN, S. Private commumcatmn, Feb. 1976.
	13	LOVASZ, LThe matrold panty problem Unpubhshed manuscript, Umverstty of Waterloo, Waterloo, Ontario, 1979.
	14	Pm'aD~a'rmOV, C.H. The complexity of the capacltated tree problem Networks 8, 3 (1978), 217-230.
	15	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	16	PAPADIMITRIOU, C H, AND YANNAKAKIS, M Unpubhshed manuscript, 1977
	17	PRIM, R.C. Shortest ~ormecuon networks and some generahzations Bell Syst Teeh. J. 36 (1957), 1389-1401.
	18	Mihalis Yannakakis, Node-and edge-deletion NP-complete problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.253-264, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804355]

CITED BY 10

	Takeo Yamada , Seiji Kataoka , Kohtaro Watanabe, Heuristic and exact algorithms for the spanning tree detection problem, Computers and Operations Research, v.32 n.2, p.239-255, February 2005
	S. Even , O. Goldreich, On the power of cascade ciphers, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.108-116, May 1985
	José R. Correa , Asaf Levin, Monotone Covering Problems with an Additional Covering Constraint, Mathematics of Operations Research, v.34 n.1, p.238-248, February 2009
	Heiner Ackermann , Alantha Newman , Heiko Röglin , Berthold Vöcking, Decision-making based on approximate and smoothed Pareto curves, Theoretical Computer Science, v.378 n.3, p.253-270, June, 2007
	M. W. Bern , H. J. Karloff , P. Raghavan , B. Schieber, Fast geometric approximation techniques and geometric embedding problems, Proceedings of the fifth annual symposium on Computational geometry, p.292-301, June 05-07, 1989, Saarbruchen, West Germany
	Faris N. Abuali , Roger L. Wainwright , Dale A. Schoenefeld, Solving the three-star tree isomorphism problem using genetic algorithms, Proceedings of the 1995 ACM symposium on Applied computing, p.337-344, February 26-28, 1995, Nashville, Tennessee, United States
	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
	Martin Fürer , Balaji Raghavachari, Approximating the minimum degree spanning tree to within one from the optimal degree, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.317-324, September 1992, Orlando, Florida, United States
	Ketan Mulmuley , Umesh V. Vazirani , Vijay V. Vazirani, Matching is as easy as matrix inversion, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.345-354, January 1987, New York, New York, United States
	Suresh Chari , Pankaj Rohatgi , Aravind Srinivasan, Randomness-optimal unique element isolation, with applications to perfect matching and related problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.458-467, May 16-18, 1993, San Diego, California, United States