Report Number: CS-TR-75-526
Institution: Stanford University, Department of Computer Science
Title: Graph theory and Gaussian elimination.
Author: Tarjan, Robert Endre
Date: November 1975
Abstract: This paper surveys graph-theoretic ideas which apply to the problem of solving a sparse system of linear equations by Gaussian elimination. Included are a discussion of bandwidth, profile, and general sparse elimination schemes, and of two graph-theoretic partitioning methods. Algorithms based on these ideas are presented.