A computationally efficient approximation to the nearest neighbor interchange metric

DOI10.1007/BF01890118zbMath0563.62033OpenAlexW2050297726MaRDI QIDQ1057598

Edward K. Brown, William H. E. Day

Publication date: 1984

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

Full work available at URL: https://doi.org/10.1007/bf01890118

zbMATH Keywords

distance measurehierarchical classificationalgorithm designmeasure of dissimilaritynearest neighbor interchange metriccomputationally efficient approximationcrossover metriclabeled leavesunrooted binary trees

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to statistics (62-04) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25)

Related Items (5)

Computing the nearest neighbor interchange metric for unlabeled binary trees is NP-complete ⋮ Probabilistic models in cluster analysis ⋮ Unnamed Item ⋮ Discriminative measures for comparison of phylogenetic trees ⋮ Optimal algorithms for comparing trees with labeled leaves

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Metrics on spaces of finite trees
• A metric and an ordering on sets
• Approximating minimum-length-sequence metrics: A cautionary note
• Counterexamples in measuring the distance between binary trees
• Comparison of phylogenetic trees
• A note on some tree similarity measures
• The complexity of computing metric distances between partitions
• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules

This page was built for publication: A computationally efficient approximation to the nearest neighbor interchange metric