Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 245-254 |
Number of pages | 10 |
Journal | Proceedings of the Annual ACM Symposium on Theory of Computing |
State | Published - May 5 1975 |
Externally published | Yes |
Event | 7th Annual ACM Symposium on Theory of Computing, STOC 1975 - Albuquerque, United States Duration: May 5 1975 → May 7 1975 |
All Science Journal Classification (ASJC) codes
- Software
Keywords
- Breadth-flrst search
- Directed graph
- Gaussian elimination
- Graph
- Lexicographlc ordering
- Perfect elimination
- Sparse linear equations
- Triangulated graph