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
Simulating binary trees on X-trees (extended abstract)
Full text PdfPdf (1.06 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: 147 - 158  
Year of Publication: 1991
ISBN:0-89791-438-4
Author
Burkhard Monien  Dept. of Math. and Computer Science, University of Paderborn, 4790 Paderborn, Germany
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): 9,   Citation Count: 1
Additional Information:

references   cited by   index terms   collaborative colleagues   peer to peer  

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/113379.113393
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
S.N. Bhatt, F.R.K. Chung, F.T. Leighton, and A.L. Rosenberg, "Optimal Simulation of Tree Machines", Proc. 27th Annual IEEE Syrup. Foundations of Computer Science, Oct. 1986, pp. 274-282.
 
2
Sandeep N. Bhatt , F. R. K. Chung , F. T. Leighton , Arnold L. Rosenberg, Universal graphs for bounded-degree trees and planar graphs, SIAM Journal on Discrete Mathematics, v.2 n.2, p.145-155, May 1989  [doi>10.1137/0402014]
3
Sandeep Bhatt , Fan Chung , Jia-Wei Hong , Arnold Rosenberg, Optimal simulations by Butterfly Networks, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.192-204, May 02-04, 1988, Chicago, Illinois, United States  [doi>10.1145/62212.62229]
 
4
F.R.K. Chllng and R.L. Graham, "On universal graphs", Proc. 2nd. Int. Conf. on Combin. Math., (A. Gerwirtz and L. Quintas, Eds.); Ann. N.Y. Acad. Sci. vo. 319, 1979, 136-140.
 
5
F.R.K. Chung and R.L. Graham, " On universal graphs for spanning trees", Journal London Ma.th. Soc., 27, 1983, 203-211.
 
6
J. Friedman , N. Pippenger, Expanding graphs contain all small trees, Combinatorica, v.7 n.1, p.71-76, Jan. 1987  [doi>10.1007/BF02579202]
 
7
B. Monien , I.H. Sudborough, Simulating binary trees on hypercubes, VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
 
8
B. Monien and I.H. Sudborough, "Embedding one Interconnection Network in Another", Computing Supp. 7, 1990, 257-282.

CITED BY
 
Ralf Klasing, Improved Compressions of Cube-Connected Cycles Networks, IEEE Transactions on Parallel and Distributed Systems, v.9 n.8, p.803-812, August 1998

INDEX TERMS

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

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

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY


General Terms:
Algorithms, Theory

Collaborative Colleagues:
Burkhard Monien: colleagues

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

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