Report Number: CS-TR-75-531
Institution: Stanford University, Department of Computer Science
Title: Algorithmic aspects of vertex elimination on directed graphs.
Author: Rose, Donald J.
Author: Tarjan, Robert Endre
Date: November 1975
Abstract: We consider a graph-theoretic elimination process which is related to performing Gaussian elimination on sparse systems of linear eauations. We give efficient algorithms to: (1) calculate the fill-in produced by any elimination ordering; (2) find a perfect elimination ordering if one exists; and (3) find a minimal elimination ordering. We also show that problems (1) and (2) are at least as time-consuming as testing whether a directed graph is transitive, and that the problem of finding a minimum ordering is NP-complete.