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

Glaucio H. Paulino, Ivan F.M. Menezes, Marcelo Gattass, Subrata Mukherjee

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)913-926
Number of pages14
JournalCommunications in Numerical Methods in Engineering
Volume10
Issue number11
DOIs
StatePublished - Nov 1994

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Engineering(all)
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A new algorithm for finding a pseudoperipheral vertex or the endpoints of a pseudodiameter in a graph'. Together they form a unique fingerprint.

Cite this