| Files: |
Description |
File size |
Format |
| Fulltext |
|
PDF (requires Acrobat Reader) |
| Fulltext |
|
PostScript (requires a PostScript Reader) |
| |
|
| Author: |
Per-Olof Fjällström |
| Article title: |
Parallel Algorithms for Searching Monotone Matrices on Coarse Grained
Multicomputers |
| Publ. type: |
Article |
| Volume: |
3 |
| Article No: |
6 |
| Language: |
English |
| Abstract [en]: |
We present parallel algorithms for geometric problems on coarse
grained multicomputers. More specifically, for a square mesh-connected p-processor
computer, we show that:
- The implicit row maxima problem on a totally monotone
n × n
matrix can be solved in
O((n/p)
log
p)
time, if
n > p2
.
- The all-farthest-neighbors problem for a convex
n
-gon
can be solved in
O(n/sqrt(p))
time, if
n > p2/4
.
- The maximum-perimeter triangle inscribed in a convex
n
-gon
can be found in
O(n/sqrt(p))
time, if
n > p2
.
The solutions to the two latter problems are based on the reduction of these
problems to searching problems in totally monotone matrices |
| PDF |
| Publisher: |
Linköping University Electronic Press |
| Year: |
1998 |
| Available: |
1998-06-17 |
| No. of pages: |
15 |
| Series: |
Linköping Electronic Articles in Computer and Information Science |
| ISSN: |
1401-9841 |
REFERENCE TO THIS PAGE:
| Fjällström, Per-Olof (1998). Parallel Algorithms for Searching Monotone Matrices on Coarse Grained
Multicomputers in Linköping Electronic Articles in Computer and Information Science, Vol. 3. http://www.ep.liu.se/ea/cis/1998/006/.
() |
|