DocumentCode
2626186
Title
Asymptotically optimal probabilistic embedding algorithms for supporting tree structured computations in hypercubes
Author
Li, Keqin ; Dorband, John E.
Author_Institution
Dept. of Math. & Comput. Sci., State Univ. of New York, New Paltz, NY, USA
fYear
1999
fDate
21-25 Feb 1999
Firstpage
218
Lastpage
225
Abstract
We show two asymptotically optimal probabilistic tree embedding algorithms in hypercubes with constant dilation. These algorithms are slight extension of the random walk algorithm. The first algorithm allows a tree node to have a stay option during each step of a random walk. The second algorithm permits varying length of random walks. Numerical data are given to demonstrate performance improvement
Keywords
hypercube networks; parallel algorithms; tree data structures; hypercubes; probabilistic embedding algorithms; random walk algorithm; tree structured computations; Computer science; Concurrent computing; Embedded computing; HTML; Heuristic algorithms; Hypercubes; Mathematics; NASA; Uniform resource locators; World Wide Web;
fLanguage
English
Publisher
ieee
Conference_Titel
Frontiers of Massively Parallel Computation, 1999. Frontiers '99. The Seventh Symposium on the
Conference_Location
Annapolis, MD
Print_ISBN
0-7695-0087-0
Type
conf
DOI
10.1109/FMPC.1999.750603
Filename
750603
Link To Document