A new algorithm for finding a pseudoperipheral vertex or the endpoints of a pseudodiameter in a graph

Based on the concept of the Laplacian matrix of a graph, this paper presents the SGPD (spectral graph pseudoperipheral and pseudodiameter) algorithm for finding a pseudoperipheral vertex or the end‐points of a pseudodiameter in a graph. This algorithm is compared with the ones by Grimes et al. (1990), George and Liu (1979), and Gibbs et al. (1976). Numerical results from a collection of benchmark test problems show the effectiveness of the proposed algorithm. Moreover, it is shown that this algorithm can be efficiently used in conjunction with heuristic algorithms for ordering sparse matrix equations. Such heuristic algorithms, of course, must be the ones which use the pseudoperipheral vertex or pseudodiameter concepts.