Göm menyn
Files: Description 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:
  1. 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 .
  2. The all-farthest-neighbors problem for a convex  n  -gon can be solved in  O(n/sqrt(p))  time, if  n > p2/4 .
  3. 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
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


Responsible for this page: Peter Berkesand
Last updated: 2017-02-21