Zurück zu den Preprints des Jahres 1995


Searching in Monge Arrays

by Girlich, E., Kovalev, M., Moshchensky, A..

Series: 1995-09, Preprints

90C10 Integer programming

We investigate the following problems in Monge arrays and their
subclasses (bitonic Monge arrays and convex arrays): (A) finding a
system of represents of all local maxima; (B) finding the minimum in
each row; (C) finding the kth smallest entry in each row; (D) sort-
ing entries in each row. We show as easy the problems become in
the subclasses of Monge arrays. Problem (A) is also considered in
multidimensional Monge arrays. An optimal algorithm is developed.