Computing the minimum fill-in is NP-complete. (English) Zbl 0496.68033


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
Full Text: DOI Link


[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.