Minimum fill-in problem of graphs
Yuan Jinjiang, Heping Zhang · Lanzhou University Institutional Repository · 1996
The computational complexity of the minimum fill-in problem of graphs is discussed in this paper. We prove that this problem is NP-complete even for bipartite graphs and square graphs. A linear time algorithm for outerplane graphs is got.