Paper Info
Title
Improved algorithms for the range next value problem and applications
Abstract
The Range Next Value problem (problem RNV) is a recent interesting variant of the range search problems, where the query is for the immediate next (or equal) value of a given number within a given interval of an array. Problem RNV was introduced and studied very recently by Crochemore et al. [Maxime Crochemore, Costas S. Iliopoulos, M. Sohel Rahman, Finding patterns in given intervals, in: Antonin Kucera, Ludek Kucera (Eds.), MFCS, 22 in: Lecture Notes in Computer Science, vol. 4708, Springer, 2007, pp. 645-656]. In this paper, we present improved algorithms for problem RNV and algorithms for extended versions of the RNV problem. We also show how this problem can be used to achieve optimal query time for a number of interesting variants of the classic pattern matching problems.
Year
DOI
Venue
2008
10.1016/j.tcs.2012.02.015
Theor. Comput. Sci.
Keywords
DocType
Volume
Improved algorithm,problem RNV,recent interesting variant,Maxime Crochemore,Antonin Kucera,interesting variant,range search problem,Range Next Value problem,RNV problem,Ludek Kucera,optimal query time,range next value problem
Conference
434,
ISSN
Citations 
PageRank 
0304-3975
11
0.57
References 
Authors
17
6
Name
Order
Citations
PageRank
Maxime Crochemore12655281.75
Costas S. Iliopoulos21534167.43
Marcin Kubica362929.26
M. Sohel Rahman448856.99
German Tischler511210.62
Tomasz Waleń670639.62