Lower bounds for row minima searching

Bradford, Phillip Gnassi; Reinert, Knut

Datensatz

DATENSATZ AKTIONENEXPORT

Zur Ablage hinzufügen

Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben

Bericht

Lower bounds for row minima searching

MPG-Autoren

/persons/resource/persons44170

Bradford, Phillip Gnassi
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45277

Reinert, Knut
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen

Es sind keine externen Ressourcen hinterlegt

Volltexte (beschränkter Zugriff)

Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.

Volltexte (frei zugänglich)

MPI-I-96-1-029.pdf
(beliebiger Volltext), 190KB

Ergänzendes Material (frei zugänglich)

Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

Zitation

Bradford, P. G., & Reinert, K.(1996). Lower bounds for row minima searching (MPI-I-1996-1-029). Saarbrücken: Max-Planck-Institut für Informatik.

Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0014-A021-C

Zusammenfassung

This paper shows that finding the row minima (maxima) in an $n \times n$ totally monotone matrix in the worst case requires any algorithm to make $3n-5$ comparisons or $4n -5$ matrix accesses. Where the, so called, SMAWK algorithm of Aggarwal {\em et al\/.} finds the row minima in no more than $5n -2 \lg n - 6$ comparisons.