algorithmic aspects of vertex elimination
We consider a graph-theoretic elimination process which is related to performing Gaussian elimination on sparse symmetric and unsymmetric systems of linear equations. We discuss good algorithms for finding elimination orderings, showing that a generalization of breadth-first search, called lexicographic search, can be used to find perfect orderings in 0(n+e) time and minimal orderings in 0(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.
graph gaussian elimination breadth-first search directed graph lexicographic ordering sparse linear equations perfect elimination triangulated graph