Computing the nearest neighbor interchange metric for unlabeled binary trees is NP-complete (Q1077168)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Computing the nearest neighbor interchange metric for unlabeled binary trees is NP-complete |
scientific article |
Statements
Computing the nearest neighbor interchange metric for unlabeled binary trees is NP-complete (English)
0 references
1986
0 references
The paper deals with the NP-completeness of computing the nearest neighbor interchange metric in the space of all unlabeled binary trees. The polynomial transformation starts with some variant of the problem PARTITION which is unfortunately not strongly NP-complete. However, the author has the analogous transformation from the 3-PARTITION problem (which is known to be NP-complete in the strong sense) and thus the announced result is correct.
0 references
dendograms
0 references
NP-completeness
0 references
