95-09
Searching in Monge Arrays
by Girlich, E.; Kovalev, M.; Moshchensky, A.
Preprint series: 95-09, Preprints
- MSC:
- 90C10 Integer programming
Abstract: We investigate the following problems in Monge arrays and theirsubclasses (bitonic Monge arrays and convex arrays): (A) finding asystem of represents of all local maxima; (B) finding the minimum ineach row; (C) finding the kth smallest entry in each row; (D) sort-ing entries in each row. We show as easy the problems become inthe subclasses of Monge arrays. Problem (A) is also considered inmultidimensional Monge arrays. An optimal algorithm is developed.
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.