Article ID: | iaor20001022 |
Country: | China |
Volume: | 9 |
Issue: | 3 |
Start Page Number: | 194 |
End Page Number: | 197 |
Publication Date: | Jul 1996 |
Journal: | Journal of Systems Science and Complexity |
Authors: | Yuan J.J., Zhang H.P. |
The computational complexity of the minimum fill-in problem of graphs is discussed in this paper. The authors prove that this problem is NP-complete even for bipartite graphs and square graphs. A linear time algorithm for outerplane graphs is obtained.