Optimal parallel construction of Hamiltonian cycles and spanning trees in random graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal parallel construction of Hamiltonian cycles and spanning trees in random graphs

Full text

Pdf (702 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures table of contents

Velen, Germany

Pages: 224 - 229

Year of Publication: 1993

ISBN:0-89791-599-2

Authors

Philip D. MacKenzie
Quentin F. Stout

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
European Comp Soc : European Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, 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/165231.165260 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.

	AV79	D. Angluin and L. G. Valiant. Fast probabilistic algorithms for hamiltonian circuits and matchings. J. Comput. System Sci., 18:155-193, 1979.
	Ber73	C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
	BFF87	B. Bollobás , A. M. Frieze , T. I. Fenner, An algorithm for finding Hamilton paths and cycles in random graphs, Combinatorica, v.7 n.4, p.327-341, Dec, 1987 [doi>10.1007/BF02579321]
	Che52	H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, 23:493-507, 1952.
	Fri87	A. M. Frieze, Parallel algorithms for finding Hamilton cycles in random graphs, Information Processing Letters, v.25 n.2, p.111-117, 6 May 1987 [doi>10.1016/0020-0190(87)90229-8]
	GMV91	Joseph Gil , Yossi Matias , Uzi Vishkin, Towards a theory of nearly constant time parallel algorithms, Proceedings of the 32nd annual symposium on Foundations of computer science, p.698-710, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185438]
	GS87	Yuri Gurevich , Saharon Shelah, Expected computation time for Hamiltonian path problem, SIAM Journal on Computing, v.16 n.3, p.486-502, June 1987 [doi>10.1137/0216034]
	Law76	E.L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York, 1976.
	Mac92	Philip D. MacKenzie, Load balancing requires &OHgr;(log*n) expected time, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.94-99, September 1992, Orlando, Florida, United States
	MV91	Yossi Matias , Uzi Vishkin, Converting high probability into nearly-constant time—with applications to parallel hashing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.307-316, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103453]
	Tho89	A. Thomason, A simple linear expected time algorithm for finding a Hamilton path, Discrete Mathematics, v.75 n.1-3, p.373-379, 1989 [doi>10.1016/0012-365X(89)90100-3]