|
|||||
|
|
| 若干NP完全问题的特殊情形 | |
| 作者姓名： | 王晓东 |
| 作者单位： | 福州大学计算机科学与技术系 |
| 摘 要： | 讨论了图算法中若干ＮＰ完全问题在所给的图是一棵树时的特殊情形－ 利用树结构的前序编号表示法提出了解树的最大独立集问题、最小顶点覆盖问题和最小支配集问题的线性时间算法－在渐近意义下这些算法都是最优算法 |
| 关 键 词： | 图 树 NP完全问题 计算复杂性 |
| 修稿时间： | 1998-09-21 |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
| 点击此处可从《福州大学学报(自然科学版)》浏览原始摘要信息 | |
| 点击此处可从《福州大学学报(自然科学版)》下载免费的PDF全文 | |