Computing the nearest neighbor interchange metric for unlabeled binary trees is NP-complete

DOI10.1007/BF01896811zbMath0594.68058MaRDI QIDQ1077168

Mirko Křivánek

Publication date: 1986

Published in: Journal of Classification (Search for Journal in Brave)

zbMATH Keywords

NP-completenessdendograms

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Other natural sciences (mathematical treatment) (92F05)

Related Items (3)

Unnamed Item ⋮ Some notes on the nearest neighbour interchange distance ⋮ APPROXIMATING THE NEAREST NEIGHBOR INTERCHARGE DISTANCE FOR NON-UNIFORM-DEGREE EVOLUTIONARY TREES

Cites Work

• Unnamed Item
• Unnamed Item
• A computationally efficient approximation to the nearest neighbor interchange metric
• Efficient algorithms for agglomerative hierarchical clustering methods
• A note on some tree similarity measures

This page was built for publication: Computing the nearest neighbor interchange metric for unlabeled binary trees is NP-complete