ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Embedding of d-dimensional grids into optimal hypercubes
Full text PdfPdf (339 KB)
Source ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the first annual ACM symposium on Parallel algorithms and architectures table of contents
Santa Fe, New Mexico, United States
Pages: 52 - 57  
Year of Publication: 1989
ISBN:0-89791-323-X
Author
M. Y. Chan  Computer Science Dept, University of Texas at Dallas, Richardson, Texas
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): 24,   Citation Count: 4
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/72935.72941
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
[BMS] S. Bettayeb, Z. Miller and I.H. Sudborough, "Embedding Grids into Hypercubes," Computer Science Program, University of Texas at Dallas, August 1987.
 
2
[C1] M.Y. Chan, "Dilation-2 Embeddings of Grids into Hypercubes," International Conference on Parallel Processing, August 1988.
 
3
[C2] M.Y. Chan, "Embedding of 3-Dimensional Grids into Optimal Hypercubes," Fourth Hypercube, Concurrent Computers, and Applications Conference, 1989. Dallas, 1988.
 
4
[G] D.S. Greenberg, "Optimal Expansion Embeddings of Meshes in Hypercubes," Technical Report YALEU/CSD/RR-535, Dept. of Computer Science, Yale University, August 1987.
 
5
[M] S. Madhavapeddy, private communications, 1988.

CITED BY  4
Shubhendu S. Mukherjee , Mark D. Hill, An evaluation of directory protocols for medium-scale shared-memory multiprocessors, Proceedings of the 8th international conference on Supercomputing, p.64-74, July 11-15, 1994, Manchester, England
D. Greenberg , S. Bhatt, Routing multiple paths in hypercubes, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.45-54, July 02-06, 1990, Island of Crete, Greece
Volker Heun , Ernst W. Mayr, Embedding graphs with bounded treewidth into their optimal hypercubes, Journal of Algorithms, v.43 n.1, p.17-50, April 2002
Volker Heun , Ernst W. Mayr, Efficient dynamic embeddings of binary trees into hypercubes, Journal of Algorithms, v.43 n.1, p.51-84, April 2002

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications; Network topology

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)


General Terms:
Algorithms, Design, Theory

Collaborative Colleagues:
M. Y. Chan: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player