Using tadpoles to reduce memory and communication requirements for exhaustive, breadth-first search using distributed computers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Using tadpoles to reduce memory and communication requirements for exhaustive, breadth-first search using distributed computers

Full text

Pdf (1.20 MB)

Source

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

Newport, Rhode Island, United States

Pages: 231 - 238

Year of Publication: 1997

ISBN:0-89791-890-8

Authors

Gene Cooperman	College of Computer Science, Northeastern University, Boston, MA
Michael Tselman	College of Computer Science, Northeastern University, Boston, MA

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): 1, Downloads (12 Months): 8, Citation Count: 0

Additional Information:

references index terms collaborative colleagues peer to peer

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/258492.258515 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	Alok Aggarwal , Richard J. Anderson , Ming-Yang Kao, Parallel depth-first search in general directed graphs, SIAM Journal on Computing, v.19 n.2, p.397-409, April 1990 [doi>10.1137/0219025]
	2	H. Amirazizi and M. Hellman, "Time-Memory- Processor Trade-Offs", IEEE Transactions on Information Theory 34(3), 1988, pp. 505-512.
	3	S.K. Chang, "Parallel Balancing of Binary Search Trees, IEEE Trans. on Computers 28, 1974, pp. 441- 445.
	4	G. Cooperman, TOP-C: a task-oriented parallel C interface, Proceedings of the High Performance Distributed Computing (HPDC '96), p.141, August 06-09, 1996
	5	Gene Cooperman, STAR/MPI: binding a parallel library to interactive symbolic algebra systems, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.126-132, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220363]
	6	Gene Cooperman , Larry Finkelstein , Michael Tselman , Bryant York, Constructing permutation representations for matrix groups, Journal of Symbolic Computation, v.24 n.3-4, p.471-488, Sept./Oct. 1997 [doi>10.1006/jsco.1997.0146]
	7	Gene Cooperman , Michael Tselman, New sequential and parallel algorithms for generating high dimension Hecke algebras using the condensation technique, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.155-160, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.236927]
	8	Proceedings of the Second International Workshop on Parallel Algorithms for Irregularly Structured Problems, September 1995
	9	V. Nageshwara Rao , Vipin Kumar, Parallel depth first search. Part I. implementation, International Journal of Parallel Programming, v.16 n.6, p.479-499, December 1987 [doi>10.1007/BF01389000]
	10	S.A.M. Makki, "Efficient distributed breadth-first search algorithm", Computer Communications 19, 1996, pp. 628-636.
	11	S. A. M. Makki , George Havas, Distributed algorithms for depth-first search, Information Processing Letters, v.60 n.1, p.7-12, Oct. 14, 1996 [doi>10.1016/S0020-0190(96)00141-X]
	12	R. Parker, oral communication.
	13	V. Nageshwara Rao , Vipin Kumar, Parallel depth first search. Part I. implementation, International Journal of Parallel Programming, v.16 n.6, p.479-499, December 1987 [doi>10.1007/BF01389000]
	14	Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
	15	R. Schroeppel and A. Shamir, "A T = O(2#/#), S = 0(2n/4 Algorithm for Certain NP-Comptete Problems", SIAM J. Computing 10(3), 1981, pp. 456-464.
	16	Steven L. Tanimoto, The elements of artificial intelligence using Common Lisp, Computer Science Press, Inc., New York, NY, 1990

INDEX TERMS

Primary Classification:
C. Computer Systems Organization
C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
C. Computer Systems Organization
C.1 PROCESSOR ARCHITECTURES

D. Software
D.1 PROGRAMMING TECHNIQUES

F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES
F.1.2 Modes of Computation
Subjects: Parallelism and concurrency
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Sorting and searching

G. Mathematics of Computing
G.4 MATHEMATICAL SOFTWARE
Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Collaborative Colleagues:

Gene Cooperman: colleagues

Michael Tselman: colleagues

Peer to Peer - Readers of this Article have also read:

Constructing reality Proceedings of the 11th annual international conference on Systems documentation
Douglas A. Powell , Norman R. Ball , Mansel W. Griffiths
Presenting computer algorithm knowledge units in computer science curriculum Journal of Computing Sciences in Colleges 16, 2
S. Krishnaprasad
Toward a real-time Ada design methodology Proceedings of the conference on TRI-ADA '90
Norman R. Howes
Fashioning conceptual constructs in Ada Proceedings of the conference on TRI-ADA '90
Robert C. Shock
Reuse: the two concurrent life cycles paradigm Proceedings of the conference on TRI-ADA '90
Richard Drake , William Ett

Adobe Acrobat

QuickTime

Windows Media Player

Real Player