Yannakakis, Mihalis Computing the minimum fill-in is NP-complete. (English) Zbl 0496.68033 SIAM J. Algebraic Discrete Methods 2, 77-79 (1981). Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 2 ReviewsCited in 175 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science 65F05 Direct numerical methods for linear systems and matrix inversion Keywords:graph chordal; sparse symmetric positive definite systems of linear equations; Gaussian elimination PDF BibTeX XML Cite \textit{M. Yannakakis}, SIAM J. Algebraic Discrete Methods 2, 77--79 (1981; Zbl 0496.68033) Full Text: DOI Link OpenURL References: [1] Garey, MichaelR.; Johnson, DavidS., Computers and intractability, (1979) · Zbl 0411.68039 [2] Garey, M. R.; Johnson, D. S.; Stockmeyer, L., Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237, (1976) · Zbl 0338.05120 [3] Rose, DonaldJ.; Read, R., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, Graph theory and computing, 183, (1972), Academic Press, New York · Zbl 0266.65028 [4] Rose, DonaldJ.; Tarjan, RobertEndre, Algorithmic aspects of vertex elimination on directed graphs, SIAM J. Appl. Math., 34, 176, (1978) · Zbl 0377.65013 [5] Rose, DonaldJ.; Tarjan, R. Endre; Lueker, GeorgeS., Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 266, (1976) · Zbl 0353.65019 [6] Yannakakis, M., Node-deletion problems on bipartite graphs, SIAM J. Comput., 10, 310, (1981) · Zbl 0468.05044 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.