Finding the closest ultrametric

DOI10.1016/j.dam.2014.07.023zbMath1303.05046OpenAlexW2142162160MaRDI QIDQ476304

J. Herrera, Sumit K. Garg

Publication date: 28 November 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.07.023

zbMATH Keywords

approximation algorithmphylogenetic reconstructionultrametriccluster deletion

Mathematics Subject Classification ID

Problems related to evolution (92D15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (2)

Ultrametric fitting by gradient descent ^* ⋮ Ultrametricity of Dissimilarity Spaces and Its Significance for Data Mining

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Correlation clustering
• The complexity of ultrametric partitions on graphs
• NP-hard problems in hierarchical-tree clustering
• Fitting distances by tree metrics with increment error
• Cluster graph modification problems
• A robust model for finding optimal evolutionary tree
• On the hardness of approximating Multicut and Sparsest-Cut
• Correlation clustering in general weighted graphs
• Clustering with qualitative information
• Fitting Tree Metrics: Hierarchical Clustering and Phylogeny
• ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
• The Complexity of Multiterminal Cuts
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Algorithms - ESA 2003
• Aggregating inconsistent information
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: Finding the closest ultrametric