skip to main content
10.1145/331697.332338acmconferencesArticle/Chapter ViewAbstractPublication PagessacConference Proceedingsconference-collections
Article
Free access

On dynamic tree growing in hypercubes

Published: 01 April 1997 Publication History
First page of PDF

References

[1]
W. Aiello and F.T. Leighton, "Coding theory, hypercube embeddings, and fault tolerance," Proc. 3rd A CM Syrup. on Parallel Algorithms and Architectures, 1991.
[2]
S. Bhatt and J.-Y. Cat, "Taking random walks to grow trees in hypercubes," JA CM, vol.40, no.3, pp.741-764, 1993.
[3]
S.N. Bhatt, F.R.K. Chtmg, F.T. Leighton, and A.L. Rosenberg, "Eftqcient embeddings of trees in hypercubes," SIAM J. Comput., vol.21, no.l, pp.151-162, 1992.
[4]
S. Bhatt, D. Greenberg, T. Leighton, and P. Liu, "Tight bounds for on-line tree embeddings," Proc. ~nd A CM-SIAM Syrup. on Discrete Algorithms, pp.344-350, 1991.
[5]
W. Dally, "Performance analysis of k-ary n-cube interconnection networks," IEEE Trans. Comput., vol.39, no.6, pp.775- 785, 1990.
[6]
W. Feller, An Introduction to Probability Theory and Its Applications, Vol.1, 3rd Ed., John Wiley & Sons, 1968.
[7]
T. Harris, The Theory of Branching Processes, Springer, Berlin, 1963.
[8]
K. Hwang, Advanced Computer Architecture: Parallelism, ScalabiIity, Programmability, McGraw-Hill, Inc., 1993.
[9]
R.M. Karp and Y. Zhang, "Randomized parallel algorithms for backtrack search and branch-and-bound computation," JA CM, vol.40, no.3, pp. 765- 789, 1993.
[10]
F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays. Trees. Hypercubes, Morgan Kaufmann Publishers, Inc., San Mateo, CA, 1992.
[11]
F.T. Leighton, et al., "Dynamic tree embeddings in butterfties and hypercubes," SIAM J. Comput., vol.21, no.4, pp.639-654, 1992.
[12]
K. Li, "Maintenance of tree structured computations on parallel and distributed computer systems," Proc. of 1I th A CAlf Syrup. on Applied Computing, pp.337-343, 1996.
[13]
J. Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984.
[14]
A.G. Ranade, "Optimal speedup for backtrack search on a butterfly network," Proc. of the 3rd A CM Syrup. on Parallel Algorithms and Architectures, pp.40-48, 1991.
[15]
A. Wagner and D.S. Corneil, "Embedding trees in a hypercube is NP-complete" SIAM J. Comput., vol.19, no.4, pp.570-590, 1990.

Cited By

View all
  • (2006)Using Communication Genre for searching with Small Display DevicesProceedings of the International Multi-Conference on Computing in the Global Information Technology10.1109/ICCGI.2006.9Online publication date: 1-Aug-2006
  • (2004)Performance evaluation of a random‐walk‐based algorithm for embedding dynamically evolving trees in hypercubic networksConcurrency and Computation: Practice and Experience10.1002/cpe.75816:13(1327-1351)Online publication date: 11-Oct-2004
  • (2002)Performance Evaluation of a Random-Walk-Based Algorithm for Embedding Dynamically Evolving Trees in ButterfliesProceedings of the 16th International Parallel and Distributed Processing Symposium10.5555/645610.661218Online publication date: 15-Apr-2002
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SAC '97: Proceedings of the 1997 ACM symposium on Applied computing
April 1997
545 pages
ISBN:0897918509
DOI:10.1145/331697
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1997

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. dynamic load distribution
  2. hypercube
  3. probabilistic analysis
  4. random walk
  5. randomized tree embedding
  6. recurrence relation

Qualifiers

  • Article

Conference

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25
The 40th ACM/SIGAPP Symposium on Applied Computing
March 31 - April 4, 2025
Catania , Italy

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)27
  • Downloads (Last 6 weeks)3
Reflects downloads up to 14 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2006)Using Communication Genre for searching with Small Display DevicesProceedings of the International Multi-Conference on Computing in the Global Information Technology10.1109/ICCGI.2006.9Online publication date: 1-Aug-2006
  • (2004)Performance evaluation of a random‐walk‐based algorithm for embedding dynamically evolving trees in hypercubic networksConcurrency and Computation: Practice and Experience10.1002/cpe.75816:13(1327-1351)Online publication date: 11-Oct-2004
  • (2002)Performance Evaluation of a Random-Walk-Based Algorithm for Embedding Dynamically Evolving Trees in ButterfliesProceedings of the 16th International Parallel and Distributed Processing Symposium10.5555/645610.661218Online publication date: 15-Apr-2002
  • (2002)Performance evaluation of a random-walk-based algorithm for embedding dynamically evolving trees in butterfliesProceedings 16th International Parallel and Distributed Processing Symposium10.1109/IPDPS.2002.1016682(8 pp)Online publication date: 2002
  • (2002)Scheduling divisible tasks on heterogeneous linear arrays with applications to layered networksProceedings 16th International Parallel and Distributed Processing Symposium10.1109/IPDPS.2002.1016659(8 pp)Online publication date: 2002
  • (2001)Optimal Dynamic Embeddings of Complete Binary Trees into HypercubesJournal of Parallel and Distributed Computing10.1006/jpdc.2001.173461:8(1110-1125)Online publication date: 1-Aug-2001
  • (1999)Asymptotically optimal probabilistic embedding algorithms for supporting tree structured computations in hypercubesProceedings. Frontiers '99. Seventh Symposium on the Frontiers of Massively Parallel Computation10.1109/FMPC.1999.750603(218-225)Online publication date: 1999
  • (1999)Efficient randomized load distribution for tree structured computations on parallel and distributed computer systemsInternational Journal of Computer Mathematics10.1080/0020716990880479071:1(21-34)Online publication date: Jan-1999
  • (1998)Performance evaluation of probabilistic tree embedding in cube-connected cyclesProceedings of the 1998 ACM symposium on Applied Computing10.1145/330560.330970(584-592)Online publication date: 27-Feb-1998
  • (1998)Asymptotically optimal randomized tree embedding in static networksProceedings of the First Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing10.1109/IPPS.1998.669951(423-430)Online publication date: 1998
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media