Algorithmic Aspects of Vertex Elimination on Directed Graphs.
Abstract
This report considers a graph-theoretic elimination process which is related to performing Gaussian elimination on sparse systems of linear equations. Efficient algorithms are given to: (1) calculate the fill-in produced by any elimination ordering; (2) find a perfect elimination ordering if on exists; and (3) find a minimal elimination ordering. It is also shown that problems (1) and (2) are at least as time-consuming as testing whether a directed graph is transitive, and that the problem of finding a minimum ordering is NP-complete.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1975
- Accession Number
- ADA020847
Entities
People
- Donald J. Rose
- Robert Tarjan
Organizations
- Harvard University