de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Lower bounds for row minima searching

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44170

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

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45277

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

1996-1-029
(beliebiger Volltext), 10KB

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: http://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.