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

It is shown first that the quest for optimal graph realizations of non- tree realisable distance matrices can be narrowed to a subclass of such matrices which satisfy a certain condition. An algorithm is then given which associates with any distance matrix D a matrix in the above subclass. If the optimal realisation of this latter matrix is known, that of D can be determined. Thus the number of distance matrices whose optimal realisations are known can be extended by the use of the algorithm.