## Abstract

Finite metric spaces are an essential tool in discrete mathematics and have applications in several areas including computational biology, image analysis, speech recognition, and information retrieval. Given any such metric \(D\) on a finite set \(X\), an important problem is to find appropriate~ways to \emph{realize}~$D$ by weighting the edges in some graph~\(G\) containing \(X\) in its vertex set such that \(D(x,y)\) equals the length of a shortest path

from \(x\) to \(y\) in \(G\) for all \(x,y \in\nobreak X\). Here we focus on realizations with minimum total edge weight, called \emph{optimal} realizations. By considering the 2-connected components and bridges in any optimal realization $G$ of $D$ we obtain an additive decomposition of \(D\) into simpler

metrics. We show that this decomposition, called the \emph{block decomposition}, is canonical in that it only depends on $D$ and {\em not} on $G$, and that the decomposition can be computed in $O(|X|^3)$ time. As well as providing a fundamental new way to decompose any finite metric space, we expect that the block decomposition will provide a useful preprocessing tool for deriving metric realizations.

from \(x\) to \(y\) in \(G\) for all \(x,y \in\nobreak X\). Here we focus on realizations with minimum total edge weight, called \emph{optimal} realizations. By considering the 2-connected components and bridges in any optimal realization $G$ of $D$ we obtain an additive decomposition of \(D\) into simpler

metrics. We show that this decomposition, called the \emph{block decomposition}, is canonical in that it only depends on $D$ and {\em not} on $G$, and that the decomposition can be computed in $O(|X|^3)$ time. As well as providing a fundamental new way to decompose any finite metric space, we expect that the block decomposition will provide a useful preprocessing tool for deriving metric realizations.

Original language | English |
---|---|

Pages (from-to) | 103-113 |

Number of pages | 11 |

Journal | Discrete Applied Mathematics |

Volume | 302 |

Early online date | 2 Jul 2021 |

DOIs | |

Publication status | Published - 30 Oct 2021 |

## Keywords

- Block decomposition
- Block realization
- Cut points
- Finite metric space
- Optimal realization