An algorithm and its role in the study of optimal graph realizations of distance matrices

DOI10.1016/0012-365X(90)90337-HzbMath0696.05048MaRDI QIDQ910418

J. M. S. Simões-Pereira

Publication date: 1990

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

non-tree realisable distance matricesoptimal graph realizations

Mathematics Subject Classification ID

Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (05C99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items

Reconstruction of graphs based on random walks ⋮ Vertex-weighted graphs: realizable and unrealizable domains ⋮ A constructive algorithm for realizing a distance matrix ⋮ New bounds on the distance Laplacian and distance signless Laplacian spectral radii ⋮ Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem ⋮ Distance spectra of graphs: a survey ⋮ Distance matrices on the \textit{H-join} of graphs: a general result and applications ⋮ Composed degree-distance realizations of graphs ⋮ Composed degree-distance realizations of graphs ⋮ Distance realization problems with applications to internet tomography ⋮ Relaxed and approximate graph realizations

Cites Work

• Unnamed Item
• On optimal embeddings of metrics in graphs
• A note on distance matrices with unicyclic graph realizations
• Submatrices of non-tree-realizable distance matrices
• Free trees and bidirectional trees as representations of psychological distance
• A note on the metric properties of trees
• A note on convexity and submatrices of distance matrices
• An Optimality Criterion for Graph Embeddings of Metrics
• Distance matrix of a graph and its realizability
• A note on the tree realizability of a distance matrix