Algorithmic aspects of vertex ellmination

We consider a graph-theoretic elimination process which is related to performin~ Gaussian elimination on sparse symmetric and unsymmetrlc systems of linear equations. We discuss good al~orlthms for finding elimination orderings, showing that a generalization of breadth-flrst search, called lexicographlc search, can be used to find perfect orderlngs in O(n+e) time and minimal orderlngs in O(ne) time, if the problem graph is undirected and has n vertices and e edges. We also give efficient (though slower) algorithms for generating such orderings on directed graphs. We claim that the minimum ordering problem for directed graphs is NP-complete, and conjecture that it is also NP-complete for undirected graphs. We include a brief discussion of the relation of elimination to transitive closure and discuss some unresolved, more general, issues.