Branch-and-bound and backtrack search on mesh-connected arrays of processors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Branch-and-bound and backtrack search on mesh-connected arrays of processors

Full text

Pdf (884 KB)

Source

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

San Diego, California, United States

Pages: 118 - 126

Year of Publication: 1992

ISBN:0-89791-483-X

Authors

Christos Kaklamanis
Giuseppe Persiano

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: 4

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/140901.140914 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	Sandeep Bhatt and Jin-Yi Cat, Take a Walk, Grow a Tree, in Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pp. 469-458.
	2	Sandeep Bhatt , David Greenberg , Tom Leighton , Pangfeng Liu, Tight bounds for on-line tree embeddings, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.344-350, January 28-30, 1991, San Francisco, California, United States
	3	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]
	4	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]
	5	Abhiram Ranade, Optimal speedup for backtrack search on a butterfly network, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.40-48, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113383]
	6	C P Schnorr , A Shamir, An optimal sorting algorithm for mesh connected computers, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.255-263, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12156]
	7	C. D. Thompson , H. T. Kung, Sorting on a mesh-connected parallel computer, Communications of the ACM, v.20 n.4, p.263-271, April 1977 [doi>10.1145/359461.359481]

CITED BY 4

	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
	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
	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
	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