Algorithmic aspects of vertex elimination
Donald J. Rose, Robert Endre Tarjan · 1975
A graph-theoretic elimination process is considered which is related to performing Gaussian elimination on sparse symmetric and unsymmetric systems of linear equations. The authors 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 O(n+e) time and minimal orderings in O(ne) time, if the problem graph is undirected and has n vertices and e edges. Also given are efficient (though slower) algorithms for generating such orderings on directed graphs. It is claimed that the minimum ordering problem for directed graphs is NP-complete, and it is conjectured that it is also NP-complete for undirected graphs. The authors include a brief discussion of the relation of elimination to transitive closure and discuss some unresolved, more general, issues.