Graph Ramsey theory and the polynomial hierarchy

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Graph Ramsey theory and the polynomial hierarchy

Full text

Pdf (698 KB)

Source

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

Atlanta, Georgia, United States

Pages: 592 - 601

Year of Publication: 1999

ISBN:1-58113-067-8

Author

Marcus Schaefer

Department of Computer Science, University of Chicago, 1100 East 58th Street, Chicago, Illinois

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 40, Citation Count: 2

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/301250.301411 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 Thierauf, The Boolean isomorphism problem, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.422, October 14-16, 1996
	2	Stefan A. Burr. An NP-complete problem in euclidean ramsey theory. Congressus Numerantium, 35:131-138, 1982.
	3	Stefan A. Burr. Determining generalized ramsey numbers is NP-hard. Ars Combinatoria, 17:21-25, 1984.
	4	Stefan A. Burr. Some undecidable problems involving the edge-coloring and vertexcoloring of graphs. Discrete Mathematics, 50:17 I-177, 1984.
	5	Stefan A. Burr. On the computational complexity of ramsey-type problems. In Nesetril & Rodl, editor, Mathematics of Ramsey Theory. Springer-Verlag, 1990.
	6	Stefan A. Burr, Jaroslav Ne~effil, and Vojtech R6dl. On the use of senders in generalized ramsey theory of graphs. Discrete Mathematics, 54:1-13, 1985.
	7	Vhclav Chvfital. Tree-complete graph ramsey numbers. Journal of Graph Theory, page 93, 1977.
	8	V/tclav Chv~tal and Frank Harary. Generalized ramsey theory for graphs, iii. small offdiagonal numbers. Pacific Journal of mathematics, 41 (2):335-345, 1972.
	9	R~inhard Diestel. Graph Theory. Springer, New York, 1997.
	10	Michael R. Garey and David S. Johnson. Computers and Intractability. Freeman, San Francisco, 1979.
	11	William fan Gasarch. A survey of recursive combinatorics. In Ershov, Goncharov, Nerode, and Remmel, editors, Handbook of Recursive Algebra. North-Holland Publishing Co.
	12	Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer. Ramsey Theory. Wiley, 1990.
	13	Frank Harary, Jaroslav Ne~eti-il, and Vojtech R6dl. Generalized ramsey theory for graphs xiv: Induced ramsey numbers. In Miroslav Fiedler, editor, Graphs and Other Combinatorial Topics, pages 90--100. Teubner, 1983.
	14	Thomas Hayes. Personal communication.
	15	Edith Hemaspaandra , Gerd Wechsung, The Minimization Problem for Boolean Formulas, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.575, October 19-22, 1997
	16	Dung T. Huynh, Deciding the inequivalence of context-free grammars with 1-letter terminal alphabet is &Sgr;p-2--complete, Theoretical Computer Science, v.33 n.2-3, p.305-326, Oct., 1984 [doi>10.1016/0304-3975(84)90092-6]
	17	Ker-I Ko and Wen-Guey Tzeng. Three Z2P- complete problems in computational learning theory. Computational Complexity, 1:269- 310, 1991.
	18	Y. Kohayakawa, H. J. Pr6mel, and Vojtech R6dl. Induced ramsey numbers. To appear in Combinatorica.
	19	Chih-Long Lin, Optimizing TRIEs for ordered pattern matching is /spl Pi//sub 2//sup P/-complete, Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), p.238, June 19-22, 1995
	20	Frank Plumpton Ramsey. On a problem of formal logic. In Proceedings of the London Mathematical Society, volume xxx of 2, pages 264-286. 1930.
	21	Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
	22	Marcus Schaefer and Pradyut Shah. Induced graph ramsey theory. Unpublished manuscript.
	23	Christopher Umans, The Minimum Equivalent DNF Problem and Shortest Implicants, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.556, November 08-11, 1998
	24	Klaus W. Wagner, The complexity of combinatorial problems with succinct input representation, Acta Informatica, v.23 n.3, p.325-356, June 1986 [doi>10.1007/BF00289117]

CITED BY 2

	Wolfgang Slany, Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete, Theoretical Computer Science, v.289 n.1, p.829-843, 23 October 2002
	Lane A. Hemaspaandra, SIGACT news complexity theory comun 37, ACM SIGACT News, v.33 n.3, September 2002