若干NP完全问题的特殊情形

• 作者: 王晓东
• 来源期刊: 福州大学学报
• 学科: 工学
• 关键词: 图 树 NP完全问题 计算复杂性
• 年，卷（期）: 1999,（5）
• 页码范围: 10-13
• 分类号: TP3
• 语种: 中文
• DOI: 10.3969/j.issn.1000-2243.1999.05.003

摘要

讨论了图算法中若干NP完全问题在所给的图是一棵树时的特殊情形.利用树结构的前序编号表示法提出了解树的最大独立集问题、最小顶点覆盖问题和最小支配集问题的线性时间算法.在渐近意义下这些算法都是最优算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王晓东	福州大学计算机科学与技术系	66	432	14.0	17.0