Revision as of 19:49, 26 February 2017 edit BlueMoonset (talk \| contribs) Autopatrolled, Extended confirmed users, Pending changes reviewers, Rollbackers 73,352 edits Reverted good faith edits by Legobot (talk): GA review was not done to criteria; it has been reverted and so is this icon. (TW) ← Previous edit		Revision as of 05:34, 2 March 2017 edit undo 116.249.112.77 (talk) →Correctness Next edit →
Line 86: ==Correctness== For the ~~algorithm~~ to be correct, it must be the case that popping and merging the top two clusters from the algorithm's stack preserves the property that the remaining clusters on the stack form a chain of nearest neighbors. Additionally, it should be the case that all of the clusters produced during the algorithm are the same as the clusters produced by a [[greedy algorithm]] that always merges the closest two clusters, even though the greedy algorithm will in general perform its merges in a different order than the nearest-neighbor chain algorithm. Both of these properties depend on the specific choice of how to measure the distance between clusters.<ref name="murtagh-tcj"/>

Nearest-neighbor chain algorithm: Difference between revisions