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.
R. W. Floyd, Algorithm 97: shortest path, Comm. ACM 5, 345 (1962)
- S. L. Hakimi and S. S. Yau, Distance matrix of a graph and its realizability, Quart. Appl. Math. 22 (1965), 305–317. MR 184873, DOI https://doi.org/10.1090/S0033-569X-1965-0184873-7
- A. J. Goldman, Realizing the distance matrix of a graph, J. Res. Nat. Bur. Standards Sect. B 70B (1966), 153–154. MR 200189
- John David Murchland, A fixed matrix method for all shortest distances in a directed graph and for the inverse problem, Universität (TH) Fridericiana zu Karlsruhe, Karlsruhe, 1970. Zur Erlangung des akademischen Grades eines Doktors der Wirtschaftswissenschaften von der Fakultät für Geistes- und Sozialwissenschaften der Universität (TH) Fridericiana zu Karlsruhe genehmigte Dissertation. MR 0321787
- K. A. Zareckiĭ, Constructing a tree on the basis of a set of distances between the hanging vertices, Uspehi Mat. Nauk 20 (1965), no. 6, 90–92 (Russian). MR 0199124
- James Turner and William H. Kautz, A survey of progress in graph theory in the Soviet Union, SIAM Rev. 12 (1970), no. suppl., iv+68. MR 268074, DOI https://doi.org/10.1137/1012125
- J. M. S. Simões Pereira, Some results on the tree realization of a distance matrix, Theory of Graphs (Internat. Sympos., Rome, 1966) Gordon and Breach, New York; Dunod, Paris, 1967, pp. 383–388 (English, with French summary). MR 0219441
- F. T. Boesch, Properties of the distance matrix of a tree, Quart. Appl. Math. 26 (1968/69), 607–609. MR 265210, DOI https://doi.org/10.1090/S0033-569X-1969-0265210-7
B. P. Shay, Some considerations of distances in a linear directed graph, M. S. thesis, E. E. Dept., Northwestern University, Evanston, Ill., 1965
- Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969. MR 0256911
Claude Berge, The theory of graphs (English translation), Methuen, 1962
A. N. Patrinos, The distance matrix of a graph and its tree realization, M. S. thesis, E. E. Dept., Northwestern Univ., Evanston, Ill., 1971
R. W. Floyd, Algorithm 97: shortest path, Comm. ACM 5, 345 (1962)
S. L. Hakimi and S. S. Yau, Distance matrix of a graph and its realizability, Quart. Appl. Math, 12, 305–317 (1965)
A. J. Goldman, Realizing the distance matrix of a graph, J. Res. Nat. Bur. Standards B70, 153–54 (1966)
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
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)
J. Turner and W. H. Kautz, A survey of progress in graph theory in the Soviet Union, SIAM Review, 12, 17 (1970)
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
F. T. Boesch, Properties of the distance matrix of a tree, Quart. Appl. Math. 16, 607–09 (1969)
B. P. Shay, Some considerations of distances in a linear directed graph, M. S. thesis, E. E. Dept., Northwestern University, Evanston, Ill., 1965
Frank Harary, Graph theory, Addison-Wesley, Reading, Mass., 1969
Claude Berge, The theory of graphs (English translation), Methuen, 1962
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
Article copyright:
© Copyright 1972
American Mathematical Society