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
(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.