Abstract | ||
---|---|---|
A class of multiway split trees is defined. Given a set of n weighted keys and a node capacity m, an algorithm is described for constructing a multiway split tree with minimum access cost. The algorithm runs in time O(mn4) and requires O(mn3) storage locations. A further refinement of the algorithm enables the factor m in the above costs to be reduced to log m. |
Year | DOI | Venue |
---|---|---|
1987 | 10.1016/0196-6774(87)90034-4 | J. Algorithms |
Keywords | Field | DocType |
optimal multiway split tree | Dynamic programming,Algorithm,Decomposition method (constraint satisfaction),Storage management,Binary search tree,Mathematics,Auxiliary memory | Journal |
Volume | Issue | ISSN |
8 | 1 | 0196-6774 |
Citations | PageRank | References |
2 | 0.42 | 4 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Shou-hsuan Stephen Huang | 1 | 174 | 59.88 |