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.

http://i.stanford.edu/pub/cstr/reports/cs/tr/75/531/CS-TR-75-531.pdf