On optimal realizations of finite metric spaces by graphs

DOI10.1007/BF02187901zbMath0641.05028MaRDI QIDQ1100481

Ingo Althöfer

Publication date: 1988

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131040

zbMATH Keywords

metric spaceweighted graphfinite metric

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Metric spaces, metrizability (54E35)

Related Items (21)

Reconstruction of graphs based on random walks ⋮ Tight span of subsets of the plane with the maximum metric ⋮ Generating sparse spanners for weighted graphs ⋮ Vertex-weighted graphs: realizable and unrealizable domains ⋮ A constructive algorithm for realizing a distance matrix ⋮ Injective optimal realizations of finite metric spaces ⋮ Reconstructibility of unrooted level-\(k\) phylogenetic networks from distances ⋮ Compatible decompositions and block realizations of finite metrics ⋮ On sparse spanners of weighted graphs ⋮ Distance spectra of graphs: a survey ⋮ Distance matrices on the \textit{H-join} of graphs: a general result and applications ⋮ Searching for realizations of finite metric spaces in tight spans ⋮ Optimal realizations and the block decomposition of a finite metric space ⋮ Composed degree-distance realizations of graphs ⋮ Recognizing and realizing cactus metrics ⋮ Composed degree-distance realizations of graphs ⋮ Certifying smoothness of discrete functions and measuring legitimacy of images ⋮ Optimal realizations of generic five-point metrics ⋮ Optimal realizations of two-dimensional, totally-decomposable metrics ⋮ Distance realization problems with applications to internet tomography ⋮ Relaxed and approximate graph realizations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On optimal embeddings of metrics in graphs
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Submatrices of non-tree-realizable distance matrices
• A note on the metric properties of trees
• A Note on Optimal and Suboptimal Digraph Realizations of Quasidistance Matrices
• Trees and Length Functions on Groups
• The theory and computation of evolutionary distances: Pattern recognition
• Duality and Distance Constraints for the Nonlinear p-Center Problem and Covering Problem on a Tree Network
• The distance matrix of a graph and its tree realization
• Diagonal tree codes
• An Optimal Diagonal Tree Code
• Distance matrix of a graph and its realizability
• Properties of the distance matrix of a tree
• A note on the tree realizability of a distance matrix
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph

This page was built for publication: On optimal realizations of finite metric spaces by graphs