%0 Journal Article %1 BANDELT199247 %A Bandelt, Hans-Jürgen %A Dress, Andreas W.M %D 1992 %J Advances in Mathematics %K decomposition metric space t-theory %N 1 %P 47 - 105 %R https://doi.org/10.1016/0001-8708(92)90061-O %T A canonical decomposition theory for metrics on a finite set %U http://www.sciencedirect.com/science/article/pii/000187089290061O %V 92 %X We consider specific additive decompositions d = d1 + … + dn of metrics, defined on a finite set X (where a metric may give distance zero to pairs of distinct points). The simplest building stones are the slit metrics, associated to splits (i.e., bipartitions) of the given set X. While an additive decomposition of a Hamming metric into split metrics is in no way unique, we achieve uniqueness by restricting ourselves to coherent decompositions, that is, decompositions d = d1 + … + dn such that for every map f:X → R with f(x) + f(y) ⩾ d(x, y) for all x, yϵX there exist maps f1, …, fn: X → R with f = f1 + … + fn and fi(x) + fi(y) ⩾ di(x, y) for all i = 1,…, n and all x, yϵX. These coherent decompositions are closely related to a geometric decomposition of the injective hull of the given metric. A metric with a coherent decomposition into a (weighted) sum of split metrics will be called totally split-decomposable. Tree metrics (and more generally, the sum of two tree metrics) are particular instances of totally split-decomposable metrics. Our main result confirms that every metric admits a coherent decomposition into a totally split-decomposable metric and a split-prime residue, where all the split summands and hence the decomposition can be determined in polynomial time, and that a family of splits can occur this way if and only if it does not induce on any four-point subset all three splits with block size two.

@article{BANDELT199247, abstract = {We consider specific additive decompositions d = d1 + … + dn of metrics, defined on a finite set X (where a metric may give distance zero to pairs of distinct points). The simplest building stones are the slit metrics, associated to splits (i.e., bipartitions) of the given set X. While an additive decomposition of a Hamming metric into split metrics is in no way unique, we achieve uniqueness by restricting ourselves to coherent decompositions, that is, decompositions d = d1 + … + dn such that for every map f:X → R with f(x) + f(y) ⩾ d(x, y) for all x, yϵX there exist maps f1, …, fn: X → R with f = f1 + … + fn and fi(x) + fi(y) ⩾ di(x, y) for all i = 1,…, n and all x, yϵX. These coherent decompositions are closely related to a geometric decomposition of the injective hull of the given metric. A metric with a coherent decomposition into a (weighted) sum of split metrics will be called totally split-decomposable. Tree metrics (and more generally, the sum of two tree metrics) are particular instances of totally split-decomposable metrics. Our main result confirms that every metric admits a coherent decomposition into a totally split-decomposable metric and a split-prime residue, where all the split summands and hence the decomposition can be determined in polynomial time, and that a family of splits can occur this way if and only if it does not induce on any four-point subset all three splits with block size two.}, added-at = {2020-12-17T11:30:57.000+0100}, author = {Bandelt, Hans-Jürgen and Dress, Andreas W.M}, biburl = {https://www.bibsonomy.org/bibtex/257b043eb48a2ae43b5cf69d439c4c7a8/tomhanika}, doi = {https://doi.org/10.1016/0001-8708(92)90061-O}, interhash = {8aa3c75fafd6d0e23b6f3a7f0d61cf7f}, intrahash = {57b043eb48a2ae43b5cf69d439c4c7a8}, issn = {0001-8708}, journal = {Advances in Mathematics}, keywords = {decomposition metric space t-theory}, number = 1, pages = {47 - 105}, timestamp = {2020-12-17T11:30:57.000+0100}, title = {A canonical decomposition theory for metrics on a finite set}, url = {http://www.sciencedirect.com/science/article/pii/000187089290061O}, volume = 92, year = 1992 }