Journal article
Efficient dynamic range minimum query
Theoretical Computer Science, Vol.656(B), pp.108-117
2016
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.
Details
- Title
- Efficient dynamic range minimum query
- Authors/Creators
- A. Heliou (Author/Creator) - Laboratoire d'Informatique de l'École PolytechniqueM. Léonard (Author/Creator) - Normandie UniversitéL. Mouchard (Author/Creator) - Laboratoire d'Informatique de l'École PolytechniqueM. Salson (Author/Creator) - Université de Lille
- Publication Details
- Theoretical Computer Science, Vol.656(B), pp.108-117
- Publisher
- Elsevier BV
- Identifiers
- 991005541791807891
- Copyright
- © 2016 Elsevier B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
76 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Computer Science, Theory & Methods
- ESI research areas
- Computer Science