Quarterly of Applied Mathematics

Quarterly of Applied Mathematics

Online ISSN 1552-4485; Print ISSN 0033-569X



The distance matrix of a graph and its tree realization

Authors: A. N. Patrinos and S. L. Hakimi
Journal: Quart. Appl. Math. 30 (1972), 255-269
MSC: Primary 05C05
DOI: https://doi.org/10.1090/qam/414405
MathSciNet review: 414405
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The results of Hakimi and Yau and others in the realization of a distance matrix are generalized to graphs (digraphs) whose branches (arcs) may have negative weights. Conditions under which such matrices have a tree, hypertree or directed tree realization are given, uniqueness of these realizations is discussed and algorithms for their construction are indicated.

References [Enhancements On Off] (What's this?)

  • [1] R. W. Floyd, Algorithm 97: shortest path, Comm. ACM 5, 345 (1962)
  • [2] S. L. Hakimi and S. S. Yau, Distance matrix of a graph and its realizability, Quart. Appl. Math, 12, 305-317 (1965) MR 0184873
  • [3] A. J. Goldman, Realizing the distance matrix of a graph, J. Res. Nat. Bur. Standards B70, 153-54 (1966) MR 0200189
  • [4] J. D. Murchland, A fixed matrix method for all shortest distances in a directed graph and for the inverse problem, Report LBS-TNT-91, Transport Network Theory Unit, London Business School, January 1969 MR 0321787
  • [5] K. A. Zaretskii, Constructing a tree on the basis of a set of distances between hanging vertices, Usp. Mat. Nauk, Akademiya Nauk SSSR, Moskovshoe Matematicheskoe Obshchestvo, 20, 90-92 (1965) (in Russian) MR 0199124
  • [6] J. Turner and W. H. Kautz, A survey of progress in graph theory in the Soviet Union, SIAM Review, 12, 17 (1970) MR 0268074
  • [7] J. Simoes-Pereira, Some results on the tree realization of a distance matrix, in Theory of graphs (P. Rosenstiehl, ed.), Gordon and Breach, N. Y., (1967), pp. 383-88 MR 0219441
  • [8] F. T. Boesch, Properties of the distance matrix of a tree, Quart. Appl. Math. 16, 607-09 (1969) MR 0265210
  • [9] B. P. Shay, Some considerations of distances in a linear directed graph, M. S. thesis, E. E. Dept., Northwestern University, Evanston, Ill., 1965
  • [10] Frank Harary, Graph theory, Addison-Wesley, Reading, Mass., 1969 MR 0256911
  • [11] Claude Berge, The theory of graphs (English translation), Methuen, 1962
  • [12] A. N. Patrinos, The distance matrix of a graph and its tree realization, M. S. thesis, E. E. Dept., Northwestern Univ., Evanston, Ill., 1971

Similar Articles

Retrieve articles in Quarterly of Applied Mathematics with MSC: 05C05

Retrieve articles in all journals with MSC: 05C05

Additional Information

DOI: https://doi.org/10.1090/qam/414405
Article copyright: © Copyright 1972 American Mathematical Society

American Mathematical Society