Name
Abstract | ||
|---|---|---|
d-dimensional array of real numbers is called monotone increasing if its entries are increasing along each dimension. Given A"n","d, a monotone increasing d-dimensional array with n entries along each dimension, and a real number x, we want to decide whether [email protected]?A"n","d, by performing a sequence of comparisons between x and some entries of A"n","d. We want to minimize the number of comparisons used. In this paper we investigate this search problem, we generalize Linial and Saks' search algorithm [N. Linial, M. Saks, Searching ordered structures, J. Algorithms 6 (1985) 86-103] for monotone three-dimensional arrays to d-dimensions for d>=4. For d=4, our new algorithm is optimal up to the lower order terms. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.disc.2007.04.067 | Discrete Mathematics |
Keywords | DocType | Volume |
partially ordered set,complexity,search algorithm,monotone multi-dimensional array,3 dimensional | Journal | 308 |
Issue | ISSN | Citations |
11 | Discrete Mathematics | 2 |
PageRank | References | Authors |
0.36 | 2 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yongxi Cheng | 1 | 125 | 15.23 |
| Xiaoming Sun | 2 | 280 | 41.19 |
| Yiqun Lisa Yin | 3 | 1138 | 75.24 |