| In this thesis, we present and analyze new algorithms for routing, sorting and dynamic searching on mesh-connected arrays of processors; also we present a lower bound concerning embeddings on faulty arrays.;In particular, we first consider the problem of permutation routing in two- and three-dimensional mesh-connected processor arrays. We present new on-line and off-line routing algorithms, all of which are optimal to within a small additive term.;Then, we show that sorting an input of size ;Furthermore, we investigate the parallel complexity of the backtrack and branch-and-bound search on the mesh-connected array. We present an ;Finally, we present a lower bound for the dilation required for any constant-congestion embedding of a fault-free three-dimensional array on a faulty three-dimensional array of the same size. |
