More time-work tradeoffs for parallel graph algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

More time-work tradeoffs for parallel graph algorithms

Full text

Pdf (1.24 MB)

Source

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

Hilton Head, South Carolina, United States

Pages: 81 - 93

Year of Publication: 1991

ISBN:0-89791-438-4

Author

Thomas H. Spencer

Computer Science Department, Rensselaer Polytechnic Institute

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/113379.113387 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	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	3	R. S. Francis , I. D. Mathieson, A Benchmark Parallel Sort for Shared Memory Multiprocessors, IEEE Transactions on Computers, v.37 n.12, p.1619-1626, December 1988 [doi>10.1109/12.9738]
	4	Zvi Galil*, Optimal parallel algorithms for string matching, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.240-248, December 1984 [doi>10.1145/800057.808687]
	5	Hillel Gazit , Gary L. Miller, An improved parallel algorithm that computes the BFS numbering of a directed graph, Information Processing Letters, v.28 n.2, p.61-65, June 24, 1988 [doi>10.1016/0020-0190(88)90164-0]
	6	Torben Hagerup, Towards optimal parallel bucket sorting, Information and Computation, v.75 n.1, p.39-51, October 1, 1987 [doi>10.1016/0890-5401(87)90062-9]
	7	Richard M. Karp, A Survey of Parallel Algorithms for Shared-Memory Machines, University of California at Berkeley, Berkeley, CA, 1988
	8	G. L. Miller and J. Reif, Parallel Tree Contraction and its application, in Proc. 26th Annual Symposium on the Foundations of Computer Science, (1985) pp. 478-489.
	9	Wolfgang J. Paul , Uzi Vishkin , Hubert Wagener, Parallel Dictionaries in 2-3 Trees, Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.597-609, July 18-22, 1983
	10	J. Reif, An optimal parallel algorithm for integer sorting, in Proc. 26th Annual Symposium on the Foundations of Computer Science, (1985) pp. 496- 5O3.
	11	T. Spencer, Time-work tradeoffs }or parallel algorithms, Tech. Report, 89-26, RPI, Troy, NY, (1989).
	12	Thomas H. Spencer, Time-work tradeoffs for parallel graph algorithms, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.425-432, January 28-30, 1991, San Francisco, California, United States
	13	R. Tarjan, U. Vishkin, An Efficient Parallel Biconnectivity Algorithm, SIAM J. Comp., 14, (1985), pp. 862-874.
	14	J. Ullman , M. Yannakakis, High-probability parallel transitive closure algorithms, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.200-209, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97686]

CITED BY 3

	Victor Y. Pan , Franco P. Preparata, Supereffective slow-down of parallel computations, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.402-409, June 29-July 01, 1992, San Diego, California, United States
	Edith Cohen, Polylog-time and near-linear work approximation scheme for undirected shortest paths, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.16-26, May 23-25, 1994, Montreal, Quebec, Canada
	Thomas H. Spencer, Time-work tradeoffs for parallel algorithms, Journal of the ACM (JACM), v.44 n.5, p.742-778, Sept. 1997