On optimal embeddings of metrics in graphs

DOI10.1016/0095-8956(84)90009-1zbMath0541.05041OpenAlexW1989964203MaRDI QIDQ794666

Wilfried Imrich

Publication date: 1984

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(84)90009-1

zbMATH Keywords

graph realizations of distance matricesoptimal realizationtree realizable metrics

Mathematics Subject Classification ID

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (28)

Nonexistence of Invariant Measures ⋮ Underlying graph and total length of optimal realizations of variable distance matrices ⋮ On optimal realizations of finite metric spaces by graphs ⋮ A constructive algorithm for realizing a distance matrix ⋮ Uniform Tree Lattices ⋮ An algorithm for tree-realizability of distance matrices^∗ ⋮ A note on distance matrices with unicyclic graph realizations ⋮ Injective optimal realizations of finite metric spaces ⋮ Subgroups of Finite Index in a Free Product With Amalgamated Subgroup ⋮ An algorithm and its role in the study of optimal graph realizations of distance matrices ⋮ Metrically independent sets in the digital plane ⋮ Cut points in metric spaces ⋮ Compatible decompositions and block realizations of finite metrics ⋮ A Note on Optimal and Suboptimal Digraph Realizations of Quasidistance Matrices ⋮ Distance spectra of graphs: a survey ⋮ A note on convexity and submatrices of distance matrices ⋮ The metric cutpoint partition problem ⋮ 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 ⋮ Optimal realizations of generic five-point metrics ⋮ Sheaves on Graphs, Their Homological Invariants, and a Proof of the Hanna Neumann Conjecture: with an Appendix by Warren Dicks ⋮ Trees related to realizations of distance matrices ⋮ Optimal realizations of two-dimensional, totally-decomposable metrics ⋮ Lossy gossip and composition of metrics ⋮ An algorithm for computing cutpoints in finite metric spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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 structure of distances in networks
• 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

This page was built for publication: On optimal embeddings of metrics in graphs