An evaluation of pseudoperipheral vertex finders for the Reverse Cuthill-McKee method for bandwidth and profile reductions of symmetric matrices

摘要

Previous publications have reviewed the main algorithms for the identification of pseudoperipheral vertices in graphs. Based on this experience, this paper evaluates seven promising methods for solving the problem of finding a proper pseudoperipheral vertex in a graph. This paper analyzes these seven pseudoperipheral vertex finders along with a new variant of Kaveh's B algorithm. This paper evaluates these algorithms with the purpose of identifying proper starting vertices for the Reverse Cuthill-McKee method. Extensive experiments among these pseudoperipheral vertex finders show that the George-Liu algorithm remains in the state of the practice to provide pseudoperipheral vertices to the Reverse Cuthill-McKee method when applied to matrices with symmetric sparsity patterns.