Abstract | ||
---|---|---|
A new proof of correctness for the Garsia-Wachs algorithm is presented. Like the well-known Hu-Tucker algorithm, the Garsia-Wachs algorithm constructs minimum cost binary trees in O(n log n) time. The new proof has a simpler structure and is free of the difficult inductions of the original. |
Year | DOI | Venue |
---|---|---|
1988 | 10.1016/0196-6774(88)90009-0 | J. Algorithms |
Keywords | Field | DocType |
garsia-wachs algorithm,new proof | Graph theory,Discrete mathematics,Combinatorics,Tree (graph theory),Correctness,Algorithm,Binary tree,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
9 | 1 | 0196-6774 |
Citations | PageRank | References |
7 | 0.69 | 1 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jeffrey H. Kingston | 1 | 336 | 38.79 |