Hamiltonian paths in infinite graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Hamiltonian paths in infinite graphs

Full text

Pdf (861 KB)

Source

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

New Orleans, Louisiana, United States

Pages: 220 - 229

Year of Publication: 1991

ISBN:0-89791-397-3

Author

David Harel

The Weizmann Institute of Science, Rehovot, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 13, Citation Count: 1

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/103418.103445 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	R. Aharoni, M. Magidor and R. A. Shore, "On the Strength of KSnig's Duality Theorem for Infinite Bipartite Graphs", Manuscript, 1990.
	2	D.R. Bean, "Effective Coloration", J. Sym. Logic 41 (1976), 469-480.
	3	D.R. Bean, "Recursive Euler and Hamiltonian Paths", Proc. Amer. Math. Soc. 55 (1976), 385-394.
	4	R. Beigel and W. I. Gasarch, unpublished resuits, 1986-1990.
	5	R. Beigel and W. I. Gasarch, "On the Complexity of Finding the Chromatic Number of a Recursive Graph", Parts I & II, Ann. Pure and Appl. Logic 45 (1989), 1-38, 227-247.
	6	S.A. Burr, "Some Undecidable Problems Involving the Edge-Coloring and Vertex Coloring of Graphs", Disc. Math. 50 (1984), 171-177.
	7	W.I. Gasarch and M. Lockwood, "The Existence of Matchings for Recursive and Highly Recursive Bipartitie Graphs", Technical report 2029, Univ. of Maryland, May 1988.
	8	W.I. Gasarch, Personal communication, 1991.
	9	David Harel, Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness, Journal of the ACM (JACM), v.33 n.1, p.224-248, Jan. 1986 [doi>10.1145/4904.4993]
	10	A. Manaster and J. Rosenstein, "Effective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall)", Proc. London Math. Soc. 3 (1972), 615-654.
	11	A. Nerode and j. Remmel, "A Survey of Lattices of R. E. Substructures", In Recursion Theory, Proc. Symp. in Pure Math. Vol. 42 (A. Nerode and R. A. Shore, eds.), Amer. Math. Soc., Providence, R. I., 1985, pp. 323-375.
	12	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987