Finding euler circuits in logarithmic parallel time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding euler circuits in logarithmic parallel time

Full text

Pdf (312 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the sixteenth annual ACM symposium on Theory of computing table of contents

Pages: 249 - 257

Year of Publication: 1984

ISBN:0-89791-133-4

Authors

B. Awerbuch
A. Israeli
Y. Shiloach

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 32, Citation Count: 3

Additional Information:

abstract 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/800057.808688 What is a DOI?

ABSTRACT

A parallel algorithm for finding Euler circuits in graphs is presented. Its depth is log |E| and it employs |E| processors. The computational model considered is the PRAM (the shared memory model). This algorithm is a nice example of utilizing another parallel algorithm that does not seem to be closely related to our problem, namely the algorithm for finding the connected components and a spanning forest of an undirected graph.

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	B. Awerbuch and Y. Shiloach, 'New Connectivity and MSF Algorithms for Ultracomputer and PRAM', Proc. of the 1983 International Conference on Parallel Processing, IEEE Computer Society Press, 175-179.
	2	Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
	3	Y. Shiloach and U. Vishkin, 'An 0(log n) Parallel Connectivity Algorithm', Journal of Algorithms 3 (1982), 57-67.

CITED BY 3

	A. Goldberg , S. Plotkin , G. Shannon, Parallel symmetry-breaking in sparse graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.315-324, January 1987, New York, New York, United States
	R M Karp , E Upfal , A Wigderson, Are search and decision programs computationally equivalent?, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.464-475, May 06-08, 1985, Providence, Rhode Island, United States
	Bonnie Berger, Simulating (logcn)-wise independence in NC, Journal of the ACM (JACM), v.38 n.4, p.1026-1046, Oct. 1991