## Maximal contour algorithms on constrained reconfigurable meshes

190.
M. Manzur Murshed and R. P. Brent,
Maximal contour algorithms on constrained reconfigurable meshes,
* Proc. 1999 International Conference on Parallel and Distributed
Processing Techniques and Applications*
(Las Vegas, Nevada),
CSREA Press, Vol. 4, 1999, 2238-2244.
Paper:
pdf (110K),
ps (98K).

## Abstract

The *Reconfigurable Mesh* (RM) has attracted criticism for its
key assumption that a message can be broadcast in constant time
independent of bus length. To account for this limit,
Beresford-Smith *et al* have recently proposed the
*k*-constrained RM model where buses of length at most
*k*, a constant, are allowed to be formed. Straightforward
simulations of optimal RM algorithms on this constrained RM model
are found to be non-optimal.
This paper presents two optimal algorithms to compute the contour of
maximal elements of a set of planar points on the *k*-constrained
RM. The first algorithm solves this problem of size *p*
in O(*p/k*) time on a *k*-constrained RM of size
*k×p*, where *k* __<__ *p*.
The second algorithm solves the same problem of size *n*
in O(*q/k*) time on a *k*-constrained RM of size
*p×q*, where *p* < *q*,
and *pq* = *kn*.

## Comments

Related papers are
[171,
174,
176,
184,
186,
191,
195].
Go to next publication

Return to Richard Brent's index page