{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,6]],"date-time":"2024-01-06T05:01:35Z","timestamp":1704517295116},"reference-count":21,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2000,6]]},"abstract":"<jats:p>A key issue in performing tree structured parallel computations is to distribute process components of a parallel program over processors in a parallel computer at run time such that both the maximum load and dilation are minimized. The main contribution of this paper is the application of recurrence relations in studying the performance of a dynamic tree embedding algorithm in hypercubes. We develop recurrence relations that characterize the expected load in randomized tree embeddings where, a tree grows by letting its nodes to take random walks of short distance. By using these recurrence relations, we are able to calculate the expected load on each processor. Therefore, for constant dilation embeddings, we are able to evaluate expected loads numerically and analytically. The applicability of recurrence relations is due to the recursive structure of trees and the fact that embeddings of the subtrees of a process node are independent of each other. Our methodology does not depend on the hypercube topology. Hence, it can be applied to studying dynamic tree growing in other networks.<\/jats:p>","DOI":"10.1142\/s0129054100000132","type":"journal-article","created":{"date-parts":[[2002,8,24]],"date-time":"2002-08-24T21:40:19Z","timestamp":1030225219000},"page":"207-230","source":"Crossref","is-referenced-by-count":7,"title":["A METHOD FOR EVALUATING THE EXPECTED LOAD OF DYNAMIC TREE EMBEDDINGS IN HYPERCUBES"],"prefix":"10.1142","volume":"11","author":[{"given":"KEQIN","family":"LI","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, State University of New York, New Paltz, New York 12561, U.S.A."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174144"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1137\/0221012"},{"key":"p_4","first-page":"344","author":"Bhatt S.","year":"1991","journal-title":"Proceedings of the 2nd ACM-SIAM Symposium on Discrete Algorithms"},{"key":"p_7","first-page":"564","author":"Gaber J.","year":"1998","journal-title":"Proceedings of the 13th Annual ACM Symposium on Applied Computing"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0030119"},{"key":"p_10","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1145\/140901.140914","author":"Kaklamanis C.","year":"1992","journal-title":"Proceedings of ACM Symposium on Parallel Algorithms and Architectures"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174145"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1137\/0221039"},{"key":"p_17","first-page":"600","author":"Li K.","journal-title":"Proceedings of International Conference on Parallel and Distributed Processing Techniques and Applications"},{"key":"p_19","first-page":"202","author":"Li K.","year":"1997","journal-title":"Proceedings of the 49th IEEE National Aerospace and Electronics Conference"},{"key":"p_20","first-page":"470","author":"Li K.","year":"1997","journal-title":"Proceedings of the 9th International Conference on Parallel and Distributed Computing and Systems"},{"key":"p_21","first-page":"584","author":"Li K.","year":"1998","journal-title":"Proceedings of the 13th Annual ACM Symposium on Applied Computing"},{"key":"p_26","first-page":"1796","author":"Li K.","journal-title":"Proceedings of International Conference on Parallel and Distributed Processing Techniques and Applications"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1080\/00207169908804790"},{"key":"p_29","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1998.1475"},{"key":"p_30","first-page":"50","volume":"1","author":"Li K.","journal-title":"Proceedings of 11th International Conference on Parallel and Distributed Computing and Systems"},{"key":"p_31","first-page":"21","volume":"126","author":"Egecioglu O.","year":"1997","journal-title":"Congressus Numerantium"},{"key":"p_32","first-page":"243","author":"Palis M.A.","year":"1995","journal-title":"Proceedings of the 7th International Conference on Parallel and Distributed Computing and Systems"},{"key":"p_34","doi-asserted-by":"publisher","DOI":"10.1145\/113379.113383"},{"key":"p_35","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1998.1440"},{"key":"p_37","doi-asserted-by":"publisher","DOI":"10.1137\/0219038"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054100000132","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,6]],"date-time":"2024-01-06T01:48:07Z","timestamp":1704505687000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054100000132"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,6]]},"references-count":21,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2000,6]]}},"alternative-id":["10.1142\/S0129054100000132"],"URL":"https:\/\/doi.org\/10.1142\/s0129054100000132","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,6]]}}}