Some Special Cases of NP-Complete Problems
Xiaodong Wang · Fuzhou daxue xuebao. Ziran kexue ban · 1999
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