The complexity of ultrametric partitions on graphs

DOI10.1016/0020-0190(88)90090-7zbMath0637.68047OpenAlexW2130327313MaRDI QIDQ1098632

Mirko Křivánek

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90090-7

zbMATH Keywords

computational complexitypolynomial algorithmcluster analysisVLSI circuitsautomated designultrametric partitionsweighted complete graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (10)

Testing metric properties ⋮ Prescribed ultrametrics ⋮ An \(O(n)\) algorithm for finding an optimal position with relative distances in an evolutionary tree ⋮ Optimal implementations of UPGMA and other common clustering algorithms ⋮ A robust model for finding optimal evolutionary tree ⋮ Finding the closest ultrametric ⋮ On the hardness of inferring phylogenies from triplet-dissimilarities ⋮ The Banaschewski compactification revisited ⋮ Ultrametric fitting by gradient descent ^* ⋮ \(l_\infty\)-approximation via subdominants.

Cites Work

• NP-hard problems in hierarchical-tree clustering
• Bottleneck extrema
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of ultrametric partitions on graphs