Distance matrix of a graph and its realizability
Authors:
S. L. Hakimi and S. S. Yau
Journal:
Quart. Appl. Math. 22 (1965), 305-317
MSC:
Primary 05.40
DOI:
https://doi.org/10.1090/qam/184873
MathSciNet review:
184873
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: The distances in a linear graph are described by a distance matrix $D$. The realizability of a given $D$ by a linear graph is discussed and conditions under which the realization of $D$ is unique are established. The optimum realization of $D$, (i.e., the realization of $D$ with “minimum total length"), is investigated. A procedure is given by which a tree realization of $D$ can be found, if such a realization exists. Finally, it is shown that a tree realization, if it exists, is unique and is the optimum realization of $D$.
- Edward F. Moore, The shortest path through a maze, Proc. Internat. Sympos. Switching Theory 1957, Part II, Harvard Univ. Press, Cambridge, Mass., 1959, pp. 285–292. MR 0114710
- Joseph B. Kruskal Jr., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc. 7 (1956), 48–50. MR 78686, DOI https://doi.org/10.1090/S0002-9939-1956-0078686-7
R. C. Prim, Shortest connection networks and some generalization, Bell System Tech. Journal 36 (1957) 1389–1401
- Richard Courant and Herbert Robbins, What Is Mathematics?, Oxford University Press, New York, 1941. MR 0005358
- Sundaram Seshu and Myril B. Reed, Linear graphs and electrical networks, Addison-Wesley Series in the Engineering Sciences, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1961. MR 0147120
- Oystein Ore, Theory of graphs, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962. MR 0150753
S. L. Hakimi, Optimum locations of switching centers and the absolute centers and medians of a graph, J. Operations Res. 12 (1964) 450–459
S. L. Hakimi and S. S. Yau, Distance matrix and the synthesis of N-port resistance networks, Network Theory Group, Tech. Report No. 5, Northwestern University, Evanston, Ill., 1963
E. F. Moore, Shortest path through a maze, Proc. Internatl. Symposium on Switching Circuits, Harvard University (1957) 285–292
J. B. Kruskal, Jr., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc. 7 (1960) 48–50
R. C. Prim, Shortest connection networks and some generalization, Bell System Tech. Journal 36 (1957) 1389–1401
R. Courant and H. Robbins, What is mathematics, Oxford University Press, London, 1941
S. Seshu and M. B. Reed, Linear graphs and electrical networks, Addison-Wesley, Reading, Mass., 1961
O. Ore, Theory of graphs, Am. Math. Soc. Colloquium Publication 38 (1962)
S. L. Hakimi, Optimum locations of switching centers and the absolute centers and medians of a graph, J. Operations Res. 12 (1964) 450–459
S. L. Hakimi and S. S. Yau, Distance matrix and the synthesis of N-port resistance networks, Network Theory Group, Tech. Report No. 5, Northwestern University, Evanston, Ill., 1963
Similar Articles
Retrieve articles in Quarterly of Applied Mathematics
with MSC:
05.40
Retrieve articles in all journals
with MSC:
05.40
Additional Information
Article copyright:
© Copyright 1965
American Mathematical Society
