On optimal realizations of finite metric spaces by graphs
type: Item
instance of: scholarly article
title: On optimal realizations of finite metric spaces by graphs
zbMATH Open document ID: 0641.05028
DOI: 10.1007/BF02187901
author: Ingo Althöfer
published in: Discrete \& Computational Geometry
publication date: 1988-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/131040
review text: Let \(G=G(V,E,w)\) be a finite undirected simple graph with vertex set V, edge set E, and \(w: E\to {\mathbb{R}}^+\) a function that assigns a positive weight (or length) to every edge of G. let \(d_ G(x,y)\) denote the length of a shortest path from vertex x to vertex y in G. The weighted graph G realizes a finite metric (M,d) if \(M\subset V\) and \(d(i,j)=d_ G(i,j)\) for all i, j of M. A realization G(V,E,w) of (M,d) is optimal if \(\sum_{e\in E}w(e)\) is minimal among all realizations of (M,d). The author presents several new results on this topic. In particular, he gives an example of a metric with a continuum of optimal realizations, thus disproving a conjecture of \textit{A. W. M. Dress} [Adv. Math. 53, 321- 402 (1984; Zbl 0562.54041)].
reviewed by: E. J. F. Primrose
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 54E35
zbMATH DE Number: 4043872
zbMATH Keywords: metric space
zbMATH Keywords: weighted graph
zbMATH Keywords: finite metric
MaRDI profile type: Publication
cites work: Properties of the distance matrix of a tree
cites work: A note on the metric properties of trees
cites work: An Optimal Diagonal Tree Code
cites work: Diagonal tree codes
cites work: Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
cites work: Q4198056
cites work: Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
cites work: Distance matrix of a graph and its realizability
cites work: Q5588444
cites work: Q3207003
cites work: Trees and Length Functions on Groups
cites work: Q5648391
cites work: On optimal embeddings of metrics in graphs
cites work: The distance matrix of a graph and its tree realization
cites work: The theory and computation of evolutionary distances: Pattern recognition
cites work: A note on the tree realizability of a distance matrix
cites work: A Note on Optimal and Suboptimal Digraph Realizations of Quasidistance Matrices
cites work: Submatrices of non-tree-realizable distance matrices
cites work: Duality and Distance Constraints for the Nonlinear p-Center Problem and Covering Problem on a Tree Network
cites work: Q5530466
Recommended article: Q5284075
Recommended article: Injective optimal realizations of finite metric spaces
Recommended article: Optimal realizations and the block decomposition of a finite metric space
Recommended article: Metric or partial metric spaces endowed with a finite number of graphs: a tool to obtain fixed point results
Recommended article: Searching for realizations of finite metric spaces in tight spans
Recommended article: Extremal results for graphs of bounded metric dimension
Recommended article: On the graphical containment of discrete metric spaces
Recommended article: Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs
Recommended article: Q3541517
Recommended article: Metric transforms of finite spaces and connected graphs
description: scientific article; zbMATH DE number 4043872