Premium
The generalized diameter of a graph
Author(s) -
Chen ChihKang Eric,
Garfinkel R. S.
Publication year - 1982
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230120310
Subject(s) - combinatorics , mathematics , graph , finite set , set (abstract data type) , algorithm , discrete mathematics , computer science , mathematical analysis , programming language
We generalize the concept of the diameter of a graph G = ( N, A ) to allow for location of points not on the nodes. It is shown that there exists a finite set of candidate points which determine this generalized diameter. Given the matrix of shortest paths, an o (| A | 2 ) algorithm is developed and tested.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom