Asymptotically optimal dynamic tree evolution by rapidly mixing random walks on regular networks

DOI10.1016/J.JPDC.2010.05.003zbMath1233.68030OpenAlexW2038432272MaRDI QIDQ666208

Keqin Li

Publication date: 7 March 2012

Published in: Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jpdc.2010.05.003

zbMATH Keywords

convergencedilationrandom walkasymptotic optimalityloaddynamic tree evolutionregular network

Mathematics Subject Classification ID

Trees (05C05) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Mathematical problems of computer architecture (68M07) Distributed systems (68M14)

Cites Work

• Performance analysis for dynamic tree embedding in \(k\)-partite networks by a random walk
• Lower bounds for dynamic tree embedding in bipartite networks
• On the performance of randomized embedding of reproduction trees in static networks
• Analysis of randomized load distribution for reproduction trees in linear arrays and rings
• Taking random walks to grow trees in hypercubes
• Randomized parallel algorithms for backtrack search and branch-and-bound computation
• A proof of alon's second eigenvalue conjecture
• Dynamic Tree Embeddings in Butterflies and Hypercubes
• Efficient randomized load distribution for tree structured computations on parallel and distributed computer systems
• Branch-and-bound and backtrack search on mesh-connected arrays of processors
• A METHOD FOR EVALUATING THE EXPECTED LOAD OF DYNAMIC TREE EMBEDDINGS IN HYPERCUBES
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Asymptotically optimal dynamic tree evolution by rapidly mixing random walks on regular networks