A new algorithm for finding a pseudoperipheral vertex or the endpoints of a pseudodiameter in a graph
Copyright policy )A new algorithm for finding a pseudoperipheral vertex or the endpoints of a pseudodiameter in a graph
AbstractBased 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.
- Pontifical Catholic University of Rio de Janeiro Brazil
- Cornell University United States
algorithm, Distance in graphs, Graphs and linear algebra (matrices, eigenvalues, etc.), endpoints, spectral graph, Matrix equations and identities, sparse matrix equations, Laplacian matrix of a graph, Computational methods for sparse matrices, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), pseudoperipheral vertex, pseudodiameter
algorithm, Distance in graphs, Graphs and linear algebra (matrices, eigenvalues, etc.), endpoints, spectral graph, Matrix equations and identities, sparse matrix equations, Laplacian matrix of a graph, Computational methods for sparse matrices, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), pseudoperipheral vertex, pseudodiameter
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).8 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!