A Note on Optimal and Suboptimal Digraph Realizations of Quasidistance Matrices
Dropping the axiom of symmetry from the definition of a metric one obtains a so-called quasimetric. Distances in a digraph G with arcs having positive weights form a quasimetric D on the set of vertices of G. One says G realizes D. If G has minimum total length of all realizations it is called optimal. The author shows that such realizations exist only in exceptional cases and introduces suboptimal realizations: If \(\tau\) is the infimum of the set of the total weight values for all realizations of D, then G is called suboptimal if for any given \(\epsilon>0\) the arcs of G can be assigned positive values such that the total length T(G) of G satisfies \(\tau<T(G)<\tau +\epsilon\). If D is a quasimetric on n elements \(x_ 1,...,x_ n\) and \(d_{ij}\) is the distance between \(x_ i\) and \(x_ j\), then the matrix with entries \(d_{ij}\) is called a quasidistance matrix. The main part of the paper is devoted to suboptimal digraph realizations of quasidistance matrices of order 2 and 3. Except for a special class of matrices such realizations are exhibited. Then several results relating quasidistance matrices to their principal submatrices and to matrices obtained by decreasing all nondiagonal entries in a column or a row are proved. Finally, the authors investigate and characterize a class of quasidistance matrices, to be called shrinkable, which by their definition and properties may be considered the analogues of tree- realizable (symmetric) distance matrices. It should be noted that a slight change in the definition of a quasimetric, i.e. the admission of \(d_{ij}=0\) if \(d_{ij}\neq 0\), and arc lengths zero in their realizations would allow to show that optimal realizations always exist. The proof is the same as for symmetric distance matrices [the reviewer, the author and \textit{Ch. M. Zamfirescu}, On optimal embeddings of metrics in graphs, J. Comb. Theory, Ser. B 36, 1-15 (1984)]. In the terminology of the present paper this would mean that suboptimal realizations always exist.
- An algorithm and its role in the study of optimal graph realizations of distance matrices
- On optimal realizations of finite metric spaces by graphs
- An Optimality Criterion for Graph Embeddings of Metrics
- On optimal embeddings of metrics in graphs
- A note on completing quasi-distance and distance matrices
- A method for the linear recording of graphs
- A note on the metric properties of trees
- A note on the tree realizability of a distance matrix
- An Optimal Diagonal Tree Code
- Diagonal tree codes
- Distance matrix of a graph and its realizability
- Duality and Distance Constraints for the Nonlinear p-Center Problem and Covering Problem on a Tree Network
- scientific article; zbMATH DE number 3648765 (Why is no real title available?)
- On optimal embeddings of metrics in graphs
- Properties of the distance matrix of a tree
- Realisierung von Metriken in Graphen
- Submatrices of non-tree-realizable distance matrices
- Technologies for constructing intelligent systems. 2: Tools
- The distance matrix of a graph and its tree realization
- The structure of distances in networks
- The theory and computation of evolutionary distances: Pattern recognition
- On optimal realizations of finite metric spaces by graphs
- A note on distance matrices with unicyclic graph realizations
- Distance spectra of graphs: a survey
- A note on completing quasi-distance and distance matrices
- An algorithm for tree-realizability of distance matrices∗
- Injective optimal realizations of finite metric spaces
- The tower matrix, an alternative to deal with distances and quasi-distances
- The graph bottleneck identity
- On optimal embeddings of metrics in graphs
- A constructive algorithm for realizing a distance matrix
This page was built for publication: A Note on Optimal and Suboptimal Digraph Realizations of Quasidistance Matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3320428)