hide
Free keywords:
-
Abstract:
We give a parallel algorithm for computing all row minima
in a totally monotone $n\times n$ matrix which is simpler and more
work efficient than previous polylog-time algorithms.
It runs in
$O(\lg n \lg\lg n)$ time doing $O(n\sqrt{\lg n})$ work on a {\sf CRCW}, in
$O(\lg n (\lg\lg n)^2)$ time doing $O(n\sqrt{\lg n})$ work on a {\sf CREW},
and in $O(\lg n\sqrt{\lg n \lg\lg n})$ time
doing $O(n\sqrt{\lg n\lg\lg n})$ work on an {\sf EREW}.
