Name
Abstract | ||
|---|---|---|
Suppose P"n={1,2,...,n} is a partially ordered set with the partial order defined by divisibility, that is, for any two elements i,j@?P"n satisfying i divides j, we have i@?"P"""nj. A table A"n={a"i|i=1,2,...,n} of real numbers is said to be consistent with P"n, provided that for any two elements i,j@?{1,2,...,n} satisfying i divides j, a"i@?a"j. Given a real number x, we want to determine whether x@?A"n, by comparing x with as few entries of A"n as possible. In this paper, we investigate the complexity @t(n), measured by the number of comparisons, of the above search problem. We present a 55n72+O(ln^2n) search algorithm for A"n and prove a lower bound (34+172160)n+O(1) on @t(n) using an adversary argument. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.tcs.2006.10.027 | Theoretical Computer Science |
Keywords | DocType | Volume |
divisibility,partially ordered set,real number,search problem,complexity,search algorithm,division poset,partial order,adversary argument,satisfiability,discrete mathematics,data structure | Journal | 370 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 0 |
PageRank | References | Authors |
0.34 | 4 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yongxi Cheng | 1 | 125 | 15.23 |
| Xi Chen | 2 | 950 | 66.32 |
| Yiqun Lisa Yin | 3 | 1138 | 75.24 |