Algorithmic Aspects of Vertex Elimination on Graphs.
Abstract
A graph-theoretic elimination process is considered which is related to performing Gaussian elimination on sparse symmetric positive definite systems of linear equations. A new linear-time algorithm is given to calculate the fill-in produced by any elimination ordering, and two new related algorithms are given for finding orderings with special properties. One algorithm, based on breadth-first search, finds a perfect elimination ordering, if any exists, in O(n+e) time, if the problem graph has n vertices and e edges. An extension of this algorithm finds a minimal (but not necessarily minimum) ordering in O(ne) time. The authors conjecture that the problem of finding a minimum ordering is NP-complete.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 10, 1975
- Accession Number
- ADA006926
Entities
People
- Donald J. Rose
- R. Endre Tarjan
Organizations
- Harvard University