Name
Abstract | ||
|---|---|---|
Optimal expected-time algorithms for (2, n) and (3, n) merge problems are given. Let ƒm(k) denote the largest n such that two ordered lists of lengths m and n can be merged in k comparisons. Our methods explore the merge trees of (2, ƒ2(k)) and (3, ƒ3(k)) problems and narrow down the choices of pairwise comparisons to minimize the expected number of comparisons even when n is not equal to ƒ2(k) or ƒ3(k). The given methods are constructive and the computed values reveal that the optimal expected value differs from the optimal worst-case value by at most 1. |
Year | DOI | Venue |
|---|---|---|
1986 | 10.1016/0196-6774(86)90026-X | Journal of Algorithms |
Field | DocType | Volume |
Discrete mathematics,Pairwise comparison,Combinatorics,Tree (graph theory),Information processing,Constructive,Algorithm,Expected value,Merge (version control),Mathematics | Journal | 7 |
Issue | ISSN | Citations |
3 | 0196-6774 | 2 |
PageRank | References | Authors |
0.39 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mai Thanh | 1 | 9 | 1.49 |
| Vangalur S. Alagar | 2 | 164 | 39.10 |
| T. D. Bui | 3 | 78 | 18.52 |