Path: utzoo!attcan!uunet!cs.utexas.edu!swrinde!emory!hubcap!sarnath
From: sarnath@sybil.cs.buffalo.edu (Ramnath Sarnath)
Newsgroups: comp.parallel
Subject: Selection/searching on matrices
Message-ID: <9489@hubcap.clemson.edu>
Date: 27 Jun 90 19:41:25 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 18
Approved: parallel@hubcap.clemson.edu

Consider the following problem:

Given a matrix in which all the rows are in non-decreasing order,
left to right, and all columns are non-decreasing top to bottom.

We wish to 

1. Search for some element "x" in the matrix.

2. Select the k-th largest element in the matrix.

I would like to know if any of you have seen such structures
arising naturally in any problem, or seen parallel algorithms
for these problems. If so, what are the time and processor
bounds acheived (assuming an nxn matrix) ?

thanx,
sarnath