The distance matrix of a graph and its tree realization

1 January 1972

journal article
Published by American Mathematical Society (AMS) in Quarterly of Applied Mathematics

Vol. 30 (3) , 255-269
https://doi.org/10.1090/qam/414405

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.

Keywords

This publication has 6 references indexed in Scilit:

A Survey of Progress in Graph Theory in the Soviet Union
SIAM Review, 1970
GRAPH THEORY
Published by Defense Technical Information Center (DTIC) ,1969
Properties of the distance matrix of a tree
Quarterly of Applied Mathematics, 1969
Realizing the distance matrix of a graph
Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1966
Distance matrix of a graph and its realizability
Quarterly of Applied Mathematics, 1965
Algorithm 97: Shortest path
Communications of the ACM, 1962