Optimal speedup for backtrack search on a butterfly network

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal speedup for backtrack search on a butterfly network

Full text

Pdf (694 KB)

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: 40 - 48

Year of Publication: 1991

ISBN:0-89791-438-4

Author

Abhiram Ranade

Computer Science Division, University of California, Berkeley, CA

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): 10, Citation Count: 14

Additional Information:

references cited by 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/113379.113383 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	Richard Karp , Yanjun Zhang, A randomized parallel branch-and-bound procedure, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.290-300, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62240]
	2	T. Leighton , M. Newman , A. G. Ranade , E. Schwabe, Dynamic tree embeddings in butterflies and hypercubes, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.224-234, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72959]
	3	Abhiram Ranade, A Simpler Analysis of the Karp-Zhang Parallel Branch-and-Bound Method, University of California at Berkeley, Berkeley, CA, 1990
	4	Yanjun Zhang , Richard M. Karp, Parallel algorithms for combinatorial search problems, 1989

CITED BY 14

	Richard M. Karp , Yanjun Zhang, Randomized parallel algorithms for backtrack search and branch-and-bound computation, Journal of the ACM (JACM), v.40 n.3, p.765-789, July 1993
	Christos Kaklamanis , Giuseppe Persiano, Branch-and-bound and backtrack search on mesh-connected arrays of processors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.118-126, June 29-July 01, 1992, San Diego, California, United States
	Keqin Li, On the performance of randomized embedding of reproduction trees in static networks, International Journal of Parallel Programming, v.31 n.5, p.393-406, October 2003
	Keqin Li, Maintenance of tree structured computations on parallel and distributed computer systems, Proceedings of the 1996 ACM symposium on Applied Computing, p.337-343, February 17-19, 1996, Philadelphia, Pennsylvania, United States
	Keqin Li, On dynamic tree growing in hypercubes, Proceedings of the 1997 ACM symposium on Applied computing, p.496-503, April 1997, San Jose, California, United States
	Sandeep Bhatt , Jin-Yi Cai, Taking random walks to grow trees in hypercubes, Journal of the ACM (JACM), v.40 n.3, p.741-764, July 1993
	Keqin Li, Performance evaluation of probabilistic tree embedding in cube-connected cycles, Proceedings of the 1998 ACM symposium on Applied Computing, p.584-592, February 27-March 01, 1998, Atlanta, Georgia, United States
	Robert D. Blumofe , Charles E. Leiserson, Space-efficient scheduling of multithreaded computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.362-371, May 16-18, 1993, San Diego, California, United States
	Bhaskar Ghosh , S. Muthukrishnan, Dynamic load balancing in parallel and distributed networks by random matchings (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.226-235, June 27-29, 1994, Cape May, New Jersey, United States
	Keqin Li, Analysis of randomized load distribution for reproduction trees in linear arrays and rings, Theoretical Computer Science, v.321 n.2-3, p.195-214, 16 August 2004
	G. Karypis , V. Kumar, Unstructured tree search on SIMD parallel computers: a summary of results, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.453-462, November 16-20, 1992, Minneapolis, Minnesota, United States
	Keqin Li, Design and analysis of asymptotically optimal randomized tree embedding algorithms in static networks, Performance Evaluation, v.60 n.1-4, p.141-163, May 2005
	G. Karypis , V. Kumar, Unstructured Tree Search on SIMD Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.5 n.10, p.1057-1072, October 1994
	Ananth Grama , Vipin Kumar, State of the Art in Parallel Search Techniques for Discrete Optimization Problems, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.28-35, January 1999