摘要
讨论了图算法中若干ＮＰ完全问题在所给的图是一棵树时的特殊情形－ 利用树结构的前序编号表示法提出了解树的最大独立集问题。
This paper discusses some special cases of NP-complete graph problems in which the given graph is a tree By means of the pre-order labeling presentation of a tree, we present several linear time algorithms for graph problems on trees These algorithms are all asymptotically optimal
出处
《福州大学学报（自然科学版）》
CAS
CSCD
1999年第5期10-13,共4页
Journal of Fuzhou University(Natural Science Edition)
基金
福建省自然科学基金
