A canonical decomposition theory for metrics on a finite set

DOI10.1016/0001-8708(92)90061-OzbMath0789.54036MaRDI QIDQ1190163

Hans-Jürgen Bandelt, Andreas W. M. Dress

Publication date: 27 September 1992

Published in: Advances in Mathematics (Search for Journal in Brave)

zbMATH Keywords

split metricstotally split-decomposable metricsplit-prime residue

Mathematics Subject Classification ID

Metric spaces, metrizability (54E35) Graph theory (05C99)

Related Items (99)

Optimality of the neighbor joining algorithm and faces of the balanced minimum evolution polytope ⋮ Combining polynomial running time and fast convergence for the disk-covering method. ⋮ Circular Networks from Distorted Metrics ⋮ On the structure of the tight-span of a totally split-decomposable metric ⋮ Phylogenetic analysis and homology ⋮ Linearly independent split systems ⋮ From weakly separated collections to matroid subdivisions ⋮ Classes of explicit phylogenetic networks and their biological and mathematical significance ⋮ Antipodal metrics and split systems ⋮ Block realizations of finite metrics and the tight-span construction. I: The embedding theorem ⋮ Group algebra of characteristic 1 and invariant distances over a finite group ⋮ Kantorovich distance on finite metric spaces: Arens-Eells norm and CUT norms ⋮ Embedding metric spaces in the rectilinear plane: a six-point criterion ⋮ Order distances and split systems ⋮ Excluded minors for the class of split matroids ⋮ Expansion of gene clusters, circular orders, and the shortest Hamiltonian path problem ⋮ Unnamed Item ⋮ The three-dimensional matching problem in kalmanson matrices ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ Tropical geometric variation of tree shapes ⋮ On a class of metrics related to graph layout problems ⋮ Fundamental polytopes of metric trees via parallel connections of matroids ⋮ A note on the uniqueness of coherent decompositions ⋮ A \(T_X\)-approach to some results on cuts and metrics ⋮ Tverberg numbers for cellular bipartite graphs ⋮ On tight spans for directed distances ⋮ R-LINE: a better randomized 2-server algorithm on the line ⋮ On the facets of the secondary polytope ⋮ Breaking the 2-competitiveness barrier for two servers in a tree ⋮ Geometry of Data ⋮ Injective split systems ⋮ Functorial hierarchical clustering with overlaps ⋮ The multi-stripe travelling salesman problem ⋮ First-order logic axiomatization of metric graph theory ⋮ The split decomposition of a \(k\)-dissimilarity map ⋮ Recent Developments in Discrete Convex Analysis ⋮ Trees, tight-spans and point configurations ⋮ Optimizing phylogenetic diversity under constraints ⋮ The polytopal structure of the tight-span of a totally split-decomposable metric ⋮ On some characterizations of antipodal partial cubes ⋮ Obtaining splits from cut sets of tight spans ⋮ Likelihood-mapping: A simple method to visualize phylogenetic content of a sequence alignment ⋮ Split decomposition over an Abelian group. I: Generalities ⋮ Even set systems ⋮ Multi-splits and tropical linear spaces from nested matroids ⋮ Splitting metrics by \(T_0\)-quasi-metrics ⋮ Compatible decompositions and block realizations of finite metrics ⋮ Mixed-up trees: the structure of phylogenetic mixtures ⋮ Distance-preserving subgraphs of Johnson graphs ⋮ Counting vertices and cubes in median graphs of circular split systems ⋮ Two novel closure rules for constructing phylogenetic super-networks ⋮ New special cases of the quadratic assignment problem with diagonally structured coefficient matrices ⋮ A note on \(M\)-convexity in polyhedral split decomposition of distances ⋮ Hyperconvexity and tight-span theory for diversities ⋮ Spectral analysis and a closest tree method for genetic sequences ⋮ An explicit computation of the injective hull of certain finite metric spaces in terms of their associated Buneman complex ⋮ \(M\)-convex functions and tree metrics ⋮ A New Tractable Case of the QAP with a Robinson Matrix ⋮ The neighbor-net algorithm ⋮ Totally splittable polytopes ⋮ Six points suffice: How to check for metric consistency ⋮ The lattice dimension of a graph ⋮ Gromov product structures, quadrangle structures and split metric decompositions for finite metric spaces ⋮ Integer linear programming as a tool for constructing trees from quartet data ⋮ Quarnet inference rules for level-1 networks ⋮ Analyzing and visualizing sequence and distance data using SPLITSTREE ⋮ Optimal algorithms for computing edge weights in planar split networks ⋮ The size of 3-compatible, weakly compatible split systems ⋮ Quartets in maximal weakly compatible split systems ⋮ Injective metrizability and the duality theory of cubings ⋮ Optimal realizations and the block decomposition of a finite metric space ⋮ The Buneman index via polyhedral split decomposition ⋮ Characterizing weak compatibility in terms of weighted quartets ⋮ Biodiversity, Shapley value and phylogenetic trees: some remarks ⋮ A solvable case of the quadratic assignment problem ⋮ Optimal realizations of generic five-point metrics ⋮ Split decomposition over an Abelian group. II: Group-valued split systems with weakly compatible support ⋮ Phylogenetic graph models beyond trees ⋮ Reconstructing phylogenies from nucleotide pattern probabilities: A survey and some new results ⋮ Retractions of finite distance functions onto tree metrics ⋮ From modular decomposition trees to rooted median graphs ⋮ Inferring evolutionary trees with strong combinatorial evidence ⋮ Betweenness structures of small linear co-size ⋮ Netlike partial cubes, V: completion and netlike classes ⋮ A comparison between two distinct continuous models in projective cluster theory: The median and the tight-span construction ⋮ On the number of vertices and edges of the Buneman graph ⋮ Some variations on a theme by Buneman ⋮ Induced cycles in crossing graphs of median graphs ⋮ Decomposition and \(l_1\)-embedding of weakly median graphs ⋮ A classification of the six-point prime metrics ⋮ The coherency index ⋮ Clustered SplitsNetworks ⋮ The tight span of an antipodal metric space. I: combinatorial properties ⋮ Optimal realizations of two-dimensional, totally-decomposable metrics ⋮ FRAÏSSÉ LIMITS FOR RELATIONAL METRIC STRUCTURES ⋮ A structured family of clustering and tree construction methods ⋮ Fishing for minimum evolution trees with neighbor-nets ⋮ Recovering a tree from the leaf colourations it generates under a Markov model ⋮ An algorithm for computing cutpoints in finite metric spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• Interval-regular graphs
• Gated sets in metric spaces
• Properties of (0,1)-matrices with no triangles
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Combinatorial approaches to multiflow problems
• Weak hierarchies associated with similarity measures - An additive clustering technique
• Submatrices of non-tree-realizable distance matrices
• A note on the metric properties of trees
• Six theorems about injective metric spaces
• Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers
• Optimal imbeddings of metrics in graphs
• The structure of distances in networks
• Hypermetric Spaces and the Hamming Cone
• Espaces Métriques Plongeables Dans Un Hypercube: Aspects Combinatoires
• On the Extreme Rays of the Metric Cone
• Recognition of Tree Metrics

This page was built for publication: A canonical decomposition theory for metrics on a finite set