Computing the Minimum Fill-In is NP-Complete
SIAM Journal on Algebraic and Discrete Methods1981Vol. 2(1), pp. 77–79
Citations Over TimeTop 10% of 1981 papers
Abstract
We show that the following problem is NP-complete. Given a graph, find the minimum number of edges (fill-in) whose addition makes the graph chordal. This problem arises in the solution of sparse symmetric positive definite systems of linear equations by Gaussian elimination.
Related Papers
- → The growth factor and efficiency of Gaussian elimination with rook pivoting(1997)46 cited
- → Fill-in comparisons between Gauss-Jordan and Gaussian eliminations(1974)6 cited
- → Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices(2003)4 cited
- → The use of small pivot perturbation in circuit analysis(1991)
- → Gaussian Elimination(2017)