An Experimental Analysis of Three Pseudo-peripheral Vertex Finders in conjunction with the Reverse Cuthill-McKee Method for Bandwidth Reduction

Abstract. The need to determine pseudoperipheral vertices arises from several graph-theoretical approaches for ordering sparse matrix equations. The results of two algorithms for finding such vertices, namely, the George-Liu and Kaveh-Bondarabady algorithms, are evaluated in this work along with a variant of the Kaveh-Bondarabady algorithm. The results suggest that the well-know George-Liu algorithm dominates the other two pseudoperipheral vertex finders mainly when considering the computational times of the algorithms.

摘要。确定伪外围顶点（pseudoperipheral vertex）的需求源于若干用于稀疏矩阵方程排序的图论方法。本文针对用于寻找此类顶点的两种算法——George-Liu算法与Kaveh-Bondarabady算法，以及Kaveh-Bondarabady算法的一种变体，开展了性能评估。研究结果表明，在考量算法计算时间的场景下，广为人知的George-Liu算法整体优于另外两种伪外围顶点查找算法。