| MINIMUM FILL-IN PROBLEM OF GRAPHS |
| |
| 作者姓名： | YUAN Jinjiang |
| |
| 作者单位： | YUAN Jinjiang (Department of Mathematics，Zhengzhou University，Zhengzhou 450052，China)ZHANG Heping (Department of Mathematics，Lanzhou University，Lanzhou 730000，China) |
| |
| 摘 要： | ＭＩＮＩＭＵＭＦＩＬＬ－ＩＮＰＲＯＢＬＥＭＯＦＧＲＡＰＨＳＹＵＡＮＪｉｎｊｉａｎｇ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＺｈｅｎｇｚｈｏｕＵｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ４５００５２，Ｃｈｉｎａ）ＺＨＡＮＧＨｅｐｉｎｇ（Ｄｅｐａｒ...
|
MINIMUM FILL-IN PROBLEM OF GRAPHS |
| |
| YUAN Jinjiang.MINIMUM FILL-IN PROBLEM OF GRAPHS[J].Journal of Systems Science and Complexity,1996(3). |
| |
| Authors: | YUAN Jinjiang |
| |
| Abstract: | 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. |
| |
| Keywords: | Graph fill-in fill-in number NP-complete |
| 本文献已被 CNKI 等数据库收录！ |
