Catalog Home Page

Efficient dynamic range minimum query

Heliou, A., Léonard, M., Mouchard, L. and Salson, M. (2016) Efficient dynamic range minimum query. Theoretical Computer Science, 656 (B). pp. 108-117.

Link to Published Version: http://dx.doi.org/10.1016/j.tcs.2016.07.002
*Subscription may be required
Free to read: https://hal.archives-ouvertes.fr/hal-01255499v2
*No subscription required

Abstract

The Range Minimum Query problem consists in answering efficiently the simple question: “what is the minimal element between two specified indices of a given array?”. In this paper we present a novel structure that offers a trade-off between time and space. Moreover we show how the structure can be easily maintained whenever an insertion, modification or deletion modifies the input sequence.

Publication Type: Journal Article
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2016 Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/34551
Item Control Page Item Control Page