A NEW ALGORITHM FOR FINDING A PSEUDOPERIPHERAL VERTEX OR THE END-POINTS OF A PSEUDODIAMETER IN A GRAPH

Based on the concept of the Laplacian matrix of a graph, this paper pr esents the SGPD (spectral graph pseudoperipheral and pseudodiameter) a lgorithm 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 t he 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 algori thms, of course, must be the ones which use the pseudoperipheral verte x or pseudodiameter concepts.