Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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.

Item 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