| 偶图的补图的侧廓问题和填充问题的NP-完全性 |
| |
| 引用本文： | 原晋江,林诒勋,刘岩,王世英.偶图的补图的侧廓问题和填充问题的NP-完全性[J].数学研究,1998,31(3):239-243. |
| |
| 作者姓名： | 原晋江 林诒勋 刘岩 王世英 |
| |
| 作者单位： | 郑州大学数学系!郑州，450052，郑州大学数学系!郑州，450052，郑州大学数学系!郑州，450052，新疆大学经济所!乌鲁木齐，830046 |
| |
| 摘 要： | 本文研究偶补图的侧廓问题和填充问题的计算复杂性，证明了：即使对直径不超过2的偶补图，侧廓问题和填充问题也是NP－完全的．
|
| 关 键 词： | 弦 区间 偶补 侧廓 填充 |
NP-completeness of the Profile Problem and the Fill-in Problem on Cobipartite Graphs |
| |
| Yuan Jinjiang, Lin Yixun, Liu Yan.NP-completeness of the Profile Problem and the Fill-in Problem on Cobipartite Graphs[J].Journal of Mathematical Study,1998,31(3):239-243. |
| |
| Authors: | Yuan Jinjiang Lin Yixun Liu Yan |
| |
| Abstract: | The computational complexity of the profile problem and the fill-in problem is studiedin this paper. Our main results are as follows: The profile problem and the fill-in problem are NPcomplete even for cobipartite graphs with diaxneter at most 2. |
| |
| Keywords: | Chordal Interval Cobipartite Profile Fill-in |
| 本文献已被 CNKI 维普 等数据库收录！ |
