A Note on Optimal and Suboptimal Digraph Realizations of Quasidistance Matrices

From MaRDI portal





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.











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)